问题
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());
}
};
