151. Reverse Words in a String

问题

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

例子

Given s = "the sky is blue",
return "blue is sky the".

分析

思路很简单，就是先翻转整个字符串，然后再逐一翻转每个单词；或者先逐一翻转每个单词，再翻转整个字符串。

问题的关键在于字符串多余空格的处理：单词之间的空格可能不止一个，字符串首尾也可能有若干空格，而题目要求输出的结果字符串头尾不能有空格，且单词间有且只能有一个空格。进一步的，题目要求使用in-place算法，即空间复杂度为O(1).

我们可以维护两个指针k和i，i负责遍历字符串，找到单词；k负责依次拷贝单词到字符串的首部，并用一个空格分割。i遇到多余的空格直接跳过。i遍历结束之后，k指向结果子字符串的末尾，直接erase掉k以后的部分即可。

要点

in-place算法一般要使用两个指针，一个指针负责遍历，另一个指针负责拷贝覆盖。

时间复杂度

O(n)

空间复杂度

O(1)

代码

class Solution {
public:
    void reverseWords(string &s) {
        reverse(s.begin(), s.end());
        int k = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] != ' ') {
                if (k != 0) s[k++] = ' ';
                int j = i;
                while (j < s.size() && s[j] != ' ')
                    s[k++] = s[j++];
                reverse(s.begin() + k - (j - i), s.begin() + k);
                i = j;
            }
        }
        s.erase(s.begin() + k, s.end());
    }
};