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 itin-placewithout allocating extra space?

Related problem:Rotate Array

Update (2017-10-16):
We have updated the function signature to accept acharacter array, so pleasereset to the default code definitionby clicking on the reload button above the code editor. Also,Run Codeis now available!

class Solution {
    public void reverseWords(char[] str) {
        int n = str.length;
        //1. reverse whole sentence
        reverse(str, 0, n - 1);
        //2. reverse word by word
        int start = 0;
        for (int i = 0; i < n; i++){
            if (str[i] == ' '){
                reverse(str, start, i - 1);
                start = i + 1;
            }
        }
        //3. reverse last word
        reverse(str, start, n - 1);
    }

    private void reverse(char[] str, int start, int end){
        while (start < end){
            char temp = str[start];
            str[start] = str[end];
            str[end] = temp;

            start++;
            end--;
        }
    }
}