151. Reverse Words in a String

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

Example 1:

Input: "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: "  hello world!  "
Output: "world! hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

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) extra space.

---

对一个字符串，以单词为单位进行逆序。注意字符串中可能会有多个连续的空格，还可能在首尾有空格。 如果允许使用额外的空间，那就好办，先把字符串分词，然后逆序拼接。代码如下：

class Solution {
public:
    void reverseWords(string& s)
    {
        string ans = "";
        int start = 0, end = 0, n = s.size();
        while (true) {
            while (start < n && s[start] == ‘ ‘)
                ++start;
            if (start >= n)
                break;
            end = start + 1;
            while (end < n && s[end] != ‘ ‘)
                ++end;
            if (end >= n)
                break;
            ans = s.substr(start, end – start) + " " + ans;
            start = end + 1;
        }
        if (end > start)
            ans = s.substr(start, end – start) + " " + ans;
        s = ans.substr(0, ans.size() – 1);
    }
};

本代码提交AC，用时9MS。

如果不借助额外空间，则只能在原字符串上进行逆序了，有意思。我们可以进行两次翻转，第一次对整个字符串翻转，然后遍历新字符串，对每个单词进行翻转。比如原字符串是”the sky is blue”，第一次翻转之后就是”eulb si yks eht”，再依次对每个单词翻转，就变成了”blue is sky the”。
我们知道对一个字符串进行翻转可以使用首尾指针的方法in-place实现，代码中为了可读性，直接调用了STL的reverse函数。

class Solution {
public:
    void reverseWords(string& s)
    {
        reverse(s.begin(), s.end()); 
        //i,j为新字符串每个单词的首尾位置，u,v为旧字符串每个单词的首尾位置
        int i = 0, j = 0, u = 0, v = 0, n = s.size();
        while (true) {
            while (u < n && s[u] == ‘ ‘)
                ++u;
            if (u >= n)
                break;
            v = u;
            while (v < n && s[v] != ‘ ‘)
                s[j++] = s[v++];
            reverse(s.begin() + i, s.begin() + j);
            if (v >= n)
                break;
            s[j++] = ‘ ‘;
            i = j;
            u = v;
        }
        if (j == 0)
            s = "";
        else if (s[j – 1] == ‘ ‘)
            s.resize(j – 1);
        else
            s.resize(j);
    }
};

本代码提交AC，用时6MS。虽然第二种方法更快，也更省空间，但是有很多边界条件很容易出错，我还是觉得第一种方法安全。
参考：http://www.cnblogs.com/grandyang/p/4606676.html