Clean Java two-pointers solution (no trim( ), no split( ), no StringBuilder)


  • 96
    public class Solution {
      
      public String reverseWords(String s) {
        if (s == null) return null;
        
        char[] a = s.toCharArray();
        int n = a.length;
        
        // step 1. reverse the whole string
        reverse(a, 0, n - 1);
        // step 2. reverse each word
        reverseWords(a, n);
        // step 3. clean up spaces
        return cleanSpaces(a, n);
      }
      
      void reverseWords(char[] a, int n) {
        int i = 0, j = 0;
          
        while (i < n) {
          while (i < j || i < n && a[i] == ' ') i++; // skip spaces
          while (j < i || j < n && a[j] != ' ') j++; // skip non spaces
          reverse(a, i, j - 1);                      // reverse the word
        }
      }
      
      // trim leading, trailing and multiple spaces
      String cleanSpaces(char[] a, int n) {
        int i = 0, j = 0;
          
        while (j < n) {
          while (j < n && a[j] == ' ') j++;             // skip spaces
          while (j < n && a[j] != ' ') a[i++] = a[j++]; // keep non spaces
          while (j < n && a[j] == ' ') j++;             // skip spaces
          if (j < n) a[i++] = ' ';                      // keep only one space
        }
      
        return new String(a).substring(0, i);
      }
      
      // reverse a[] from a[i] to a[j]
      private void reverse(char[] a, int i, int j) {
        while (i < j) {
          char t = a[i];
          a[i++] = a[j];
          a[j--] = t;
        }
      }
      
    }

  • 4
    C

    The code could be slightly faster by running the space cleaning function first, since less iterations would be needed in the reverse function loops.


  • 0

    This solution is super concise and understandable. Thanks! Appreciate your work.


  • 0
    D

    Very clean logic without java libraries

    I would like to share my version of clean spaces

    public String cleanSpaces(char[] ca, int len) {
        int index = 0;
        for(int i = 0; i < len; ++i){
            if(i > 0 && ca[i] == ' ' && ca[i - 1] == ' ') continue;
            ca[index++] = ca[i]; 
        }
        return new String(ca).substring(0, index);
    }

  • 1
    M

    @daiqiang1117 Please test before post, the leading space is not trimmed.


  • 1
    C

    This is supposed to be the highest accepted solution.
    Resolve the problem from the bottom.
    I don't understand why the answer with Java library got sooooo many upvotes.


  • 0
    F

    @daiqiang1117 Great! just a small change : return new String(ca).substring(0, index).trim(). So the leading and tail spaces could be removed


  • 0

    I'm just wondering, since the cleanSpaces method returns a new String. does that considered as using extra space?


  • 0
    J

    OP is such a genius!而且长得也帅😆


  • 0
    A

    @jeantimex said in Clean Java two-pointers solution (no trim( ), no split( ), no StringBuilder):

    void reverseWords(char[] a, int n) {
    int i = 0, j = 0;

    while (i < n) {
      while (i < j || i < n && a[i] == ' ') i++; // skip spaces
      while (j < i || j < n && a[j] != ' ') j++; // skip non spaces
      reverse(a, i, j - 1);                      // reverse the word
    }
    

    }

    Hi,please explain why use the condition of i < j in "while (i < j || i < n && a[i] == ' ')" and j <i in "while (j < i || j < n && a[j] != ' ')", thank you!!!


  • 0
    S

    @abc_begin
    i and j both starts from 0, i is the start pointer, j is the end pointer
    (1) while(i<n && a[i]==' ') i++ is to skip the leading spaces before every word.
    (2) while (j<i) points j to the same position as i, because i has already skipped the leading spaces in prior while
    (3) while(j<n && a[j]!=' ') find the whole word starts from i, ends at j until a[j] is ' ' or j<n
    (4) while(i<j) i is the start index of last word, j-1 is the end index of the last word, points i to the same position as j, then start finding the next word


  • 0
    G

    more clear solution

    public class Solution {
        public String reverseWords(String s) {
            char [] A = s.toCharArray();
            reverse(A, 0, s.length() - 1);
            int pre = -1;
            for (int i = 0; i <= s.length(); i++) {
                if (i == s.length() || A[i] == ' ') {
                    reverse(A, pre + 1, i - 1);
                    pre = i;
                }
            }
            int res = 0;
            boolean firstWord = true;
            for (int i = 0; i < A.length; i++) {
                if (A[i] != ' ') {
                    if (!firstWord && A[i - 1] == ' ') {
                        A[res++] = ' ';
                    }
                    A[res++] = A[i]; 
                    firstWord = false;
                }
            }
            return (new String(A)).substring(0, res);
        }
        
        public void reverse(char [] A, int s, int e) {
            while (s < e) {
                char tmp = A[s];
                A[s] = A[e];
                A[e] = tmp;
                s++;
                e--;
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.