Problem description:

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

Example:

Input: ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]
Note:

A word is defined as a sequence of non-space characters.
The input string does not contain leading or trailing spaces.
The words are always separated by a single space.
Follow up: Could you do it in-place without allocating extra space?

Solution:

We can reverse the string first, then use two pointers to find space ' '. 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    void reverseWords(vector<char>& str) {
        reverse(str.begin(), str.end());
        int left= 0, right= 0, n= str.size();
        while(right< n){
            while(right< n && str[right]!= ' ') right++;
            reverse(str.begin()+left, str.begin()+right);
            left= ++right;
        }
    }
};

time complexity: $O(n)$

reference:
https://goo.gl/mLq9PF
https://goo.gl/PztRhh