Given an input string, reverse the string word by word.

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

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

The idea is to solve this in-place without extra space.
We can first 1) flip the string and then 2) flip the words inside the string.
Since this problem regardless of multiple spaces, it is relatively easier.

class Solution {
    public void reverseWords(char[] s) {
       // reverse the whole seq
       reverse(s, 0, s.length-1);
       // reverse each word inside the seq
       int start = 0;
       int len = s.length;
       for(int i=0;i<len;i++){
            if(s[i]==' '){ // meet a separation
                reverse(s, start, i-1);
                start = i+1;
            }
        }
        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--;
        }
    }

}