My Java solution with explanation


  • 78
    X
    public void reverseWords(char[] s) {
        // Three step to reverse
        // 1, reverse the whole sentence
        reverse(s, 0, s.length - 1);
        // 2, reverse each word
        int start = 0;
        int end = -1;
        for (int i = 0; i < s.length; i++) {
            if (s[i] == ' ') {
                reverse(s, start, i - 1);
                start = i + 1;
            }
        }
        // 3, reverse the last word, if there is only one word this will solve the corner case
        reverse(s, start, s.length - 1);
    }
    
    public void reverse(char[] s, int start, int end) {
        while (start < end) {
            char temp = s[start];
            s[start] = s[end];
            s[end] = temp;
            start++;
            end--;
        }
    }

  • 33
    S

    Great Solution! I just made little change to include the last word into the loop.

    public void reverseWords(char[] s){
    		reverseWords(s,0,s.length-1);
    		for(int i = 0, j = 0;i <= s.length;i++){
    			if(i==s.length || s[i] == ' '){
    				reverseWords(s,j,i-1);
    				j = i+1;
    			}
    		}
    	}
    
    	private void reverseWords(char[] s, int begin, int end){
    		while(begin < end){
    			char c = s[begin];
    			s[begin] = s[end];
    			s[end] = c;
    			begin++;
    			end--;
    		}
    	}

  • 15
    Y

    the ** end ** variable did not used, bro.

    You may consider to delete the line:

    int end = -1;

  • -1
    S

    Can anyone tell me why I change the code to "if(s[i] == ' ' || i == s.length)" will cause runtime error?


  • 0
    1

    in the for loop , i<=s.length. s[s.length] will cause indexoutofbound error. But if you check i==s.length before you check s[i], it will skip checking s[i] because the first clause returns true.


  • 0
    I

    I am always wondering, when you are calling recursive function, you are allocating space in stack memory. Does it still count in place O(1) ?


  • 0
    I

    The way how || works is that it checks first expression first, if it returns true, then the second expression will be skipped. Same for &&, if the first expression return false, then the second expression will be skipped too.


  • 0
    W

    Correct. If there is a recursion, typically it will not be O(1).
    However, this solution has no recursion.


  • 0
    K

    @wei88 why the parameter is char[], isn't it should be a string?


  • 0
    W

    @kenwang
    Java solution provides char[] as argument.
    Java has no pointer. A String is an immutable object. So if the return value is void, you need a char[] instead of a string, no matter whether your algorithm is in place or not.

    C++ can do in place if the given argument is String.


  • 0
    X

    But if there are multiple spaces between words, how do you solve it to only one space?


  • 0
    W

    @xiaoweiweionly this solution works with multiple spaces


  • 0
    J

    Very smart solution. For the explanation, whether or not there is only word, we have to reverse the last word. Because in the for loop, the last word would't be reversed.


  • 0
    F

    So the time complexity should be O(mn) right? m means the length of the word, n means the length of the whole char array.


  • 2

    @FreeLance not quite, it's more like 3n which is O(n). Here's the break down.

    1. reverse the whole string, this is n steps.
    2. advance right pointer to find end of word, the right pointer just advances through whole string and never backtracks, so this is n iterations.
    3. reverse the word found, if word is length m, this is m steps, but consider all words together will be n, so this is also n steps total for all words.

    total is 3n which is just O(n).


  • 0
    Y
    This post is deleted!

  • 0
        public void reverseWords(char[] cs) {
          int n = cs.length;  
          reverse(cs, 0, n - 1);
          
          int s = 0;  
          for(int i = 0; i < n; i++){
            if(cs[i] == ' '){
              reverse(cs, s, i - 1);
              s = i + 1;  
            }  
          }
          reverse(cs, s, n - 1); 
        }
        
        void reverse(char[] cs, int s, int e){
          while(s < e){
            char t = cs[s];
            cs[s] = cs[e];
            cs[e] = t; 
            s++;
            e--;
          }  
        }

Log in to reply
 

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