問題

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

例子

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

分析

思路很簡(jiǎn)單，就是先翻轉(zhuǎn)整個(gè)字符串，然后再逐一翻轉(zhuǎn)每個(gè)單詞；或者先逐一翻轉(zhuǎn)每個(gè)單詞，再翻轉(zhuǎn)整個(gè)字符串。

問題的關(guān)鍵在于字符串多余空格的處理：?jiǎn)卧~之間的空格可能不止一個(gè)，字符串首尾也可能有若干空格，而題目要求輸出的結(jié)果字符串頭尾不能有空格，且單詞間有且只能有一個(gè)空格。進(jìn)一步的，題目要求使用in-place算法，即空間復(fù)雜度為O(1).

我們可以維護(hù)兩個(gè)指針k和i，i負(fù)責(zé)遍歷字符串，找到單詞；k負(fù)責(zé)依次拷貝單詞到字符串的首部，并用一個(gè)空格分割。i遇到多余的空格直接跳過。i遍歷結(jié)束之后，k指向結(jié)果子字符串的末尾，直接erase掉k以后的部分即可。

要點(diǎn)

in-place算法一般要使用兩個(gè)指針，一個(gè)指針負(fù)責(zé)遍歷，另一個(gè)指針負(fù)責(zé)拷貝覆蓋。

時(shí)間復(fù)雜度

O(n)

空間復(fù)雜度

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