Leetcode 186 - Reverse Words in a String II

http://buttercola.blogspot.com/2015/08/leetcode-reverse-words-in-string-ii.html

Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.

The input string does not contain leading or trailing spaces and the words are always separated by a single space.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Could you do it in-place without allocating extra space?

    public void reverseWords(char[] s) {

        if (s == null || s.length <= 1) {

            return;

        }

         

        int i = 0;

        int j = s.length - 1;

        while (i < j) {

            swap(s, i, j);

            i++;

            j--;

        }

         

        // Step 2: swap again within a token

        i = 0;

        j = 0;

        while (j < s.length) {

            while (j < s.length && s[j] != ' ') {

                j++;

            }

             

            int m = i;

            int n = j - 1;

            while (m < n) {

                swap(s, m, n);

                m++;

                n--;

            }

             

            i = j + 1;

            j = i;

        }

    }

     

    private void swap(char[] s, int i, int j) {

        char tmp = s[i];

        s[i] = s[j];

        s[j] = tmp;

    }

http://betterpoetrythancode.blogspot.com/2015/02/reverse-words-in-string-ii-leetcode.html

   public void reverseWords(char[] s) {  
     if(s==null||s.length==0)  
       return;  
     reverse(s,0,s.length-1);  
     for(int left=0;left<s.length;left++)  
     {  
       if(s[left]!=' ')  
       {  
         int right=left;  
         while(right<s.length&&s[right]!=' ')  
           right++;  
         reverse(s,left,right-1);  
         left=right;  
       }  
     }  
   }  
   public void reverse(char[] chars, int start,int end)  
   {  
     for(int i=start,j=end;i<j;i++,j--)  
     {  
       char tmp=chars[i];  
       chars[i]=chars[j];  
       chars[j]=tmp;  
     }  
   }  

http://www.danielbit.com/blog/puzzle/leetcode/leetcode-reverse-words-in-a-string-ii

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

1）如果是Java，应该跟面试官指出String是immutable，所以需要用char array来做。
2）follow-up问题：k-step reverse。也就是在第二部翻转的时候，把k个单词看作一个长单词，进行翻转。

https://leetcode.com/discuss/24227/my-java-solution-with-explanation

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--; } }

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--;
        }
    }