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?

Analysis:

We reverse the whole string first, and then reverse each word again.

Solution:

public class Solution {    public void reverseWords(char[] s) {        reverse(s,0,s.length-1);        int p1=0,p2=0;        while (p1 < s.length){            p2 = p1;            while (p2 < s.length && s[p2]!=' '){                p2++;            }            reverse(s,p1,p2-1);            p1 = p2+1;        }    }    public void reverse(char[] s, int start, int end){        while (start < end){            char temp = s[start];            s[start++] = s[end];            s[end--] = temp;        }    }}