186. Reverse Words in a String II (Medium)

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?

Related problem: Rotate Array

Solution 1: String

这道题让我们翻转一个字符串中的单词，跟之前那题Reverse Words in a String没有区别，由于之前那道题我们就是用in-place的方法做的，而这道题反而更简化了题目，因为不考虑首尾空格了和单词之间的多空格了，方法还是很简单，先把每个单词翻转一遍，再把整个字符串翻转一遍，或者也可以调换个顺序，先翻转整个字符串，再翻转每个单词，参见代码如下：

version 1: 6ms

class Solution {
public:
    void reverseWords(string &s) {
        reverse(s.begin(), s.end());
        int left = 0;
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || s[i] == ' ') {
                reverse(s.begin()+left, s.begin()+i);
                left = i+1;
            }
        }
    }
};

version 2: 6ms

class Solution {
public:
    void reverseWords(string &s) {
        reverse(s, 0, s.size()-1);
        int left = 0;
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || s[i] == ' ') {
                reverse(s, left, i-1);
                left = i+1;
            }
        }
    }

    void reverse(string &s, int left, int right) {
        while (left < right) {
            swap(s[left++], s[right--]);
        }
    }
};

Solution 2: stringstream 9ms

class Solution {
public:
    void reverseWords(string &s) {
        istringstream is(s);
        string word;
        is >> s;
        while (is >> word) s = word + ' ' + s;
    }
};