# 186 Reverse Words in a String II

the sky is blue -> blue is the sky

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

Concept:

如果不需要in-place的話就很直覺，把input string用" "split後，

照相反順序放入一個新的stringbuilder就好。

Concept:

為了達到in-place的要求，只能在原本的String中操作。

寫一個function: reverse()處理所有字串的reverse，

reverse(String)，之後再一一把每個單字reverse()即可得到答案。

Pseudocode:

Main:
String input = reverse(input);
int j=0//record the start of a word
for(int i=0; i<input.length; i++)
    if current element is ' ', means reach a word's end
        input.substring(j,i).reverse()
        j=i+1

return input

reverse():

實測的時候發現有問題，當String中沒有任何空格時，就不會跑到迴圈內的reverse()，

e.g "ab" 輸出應該要是"ab"，但不會進去迴圈內的reverse()

後來發現應該要在從迴圈出來後最後再reverse一次，

這樣String中的最後一個word才會被reverse到。

完整程式碼

public class Solution {
    public void reverseWords(char[] s) {
        if(s.length == 0 || s.length == 1)   return;
        reverse(s,0,s.length-1);
        int j=0;
        for(int i=0; i<s.length; i++){
            if(s[i]==' '){
                reverse(s, j, i-1);
                j=i+1;
            }
        }

        reverse(s, j, s.length - 1);
    }

    void reverse(char[] s, int x, int y){
        while(x <= y){
            char c = s[y];
            s[y] = s[x];
            s[x] = c;
            x++;
            y--;
        }
    }
}