Reverse Words in a String

Desicription

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

Example: 

1
2
Input: "the sky is blue",
Output: "blue is sky the".

Note:

  • A word is defined as a sequence of non-space characters.
  • Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
  • You need to reduce multiple spaces between two words to a single space in the reversed string.

Follow up: For C programmers, try to solve it in-place in O(1) space.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void reverseWords(string &s) {
        string res;
        int right = s.size();
        for(int left = right - 1; left >= 0; left--) {
            if(s[left] == ' ')
                right = left;
            else if(left == 0 || s[left-1] == ' ') {
                if(res.size())
                    res += " ";
                res += s.substr(left, right-left);
            }
        }
        s = res;
    }
};