題目網址：https://leetcode.cn/problems/reverse-words-in-a-string/

題意：給一 string s, 請你反轉 s 中單字的順序。

單字是由非空格 char 所組成的 string, s 中至少使用一空格將 string 中的單字分開。

注意：s 中可能會存在前導空格、尾隨空格 or 單字間的多個空格。返回的 output 中, 單字間應當僅用單個空格分隔, 且不包含任何額外的空格。

進階：如果 s 在你使用的語言中是可變的, 設計 $O(1)$ space 的演算法。

Solution 1：

想法：利用 Stack, 先將分割出每個 word, 並把 word 加到 stack 中, 然後再一一 pop 出來, 要注意最後一個 word 後面不能有空格

class Solution {
public:
    string reverseWords(string s) {
        const int n = s.size();
        stack<string> stk; // 讓後面的 word 先被 pop 出去

        for (int i = 0; i < n; ++i) {
            if (s[i] == ' ') {
                continue;
            }

            string word;
            while (i < n && s[i] != ' ') {
                word += s[i++];
            }
            stk.emplace(word);
        }

        s = "";
        while (!stk.empty()) {
            s += stk.top();
            stk.pop();

            // 不是最後一個 word 的話, 則要加 " "
            if (!stk.empty()) {
                s += " ";
            }
        }

        return s;
    }
};
  • time：$O(n)$ ➔ 遍歷 s
  • space：$O(n)$ ➔ stk 儲存每個 word

Solution 2：

想法：利用 Two Pointers 先去除多餘的空格(可參考 27. Remove Element), 然後 reverse string, 最後再 reverse 每一個 word

class Solution {
public:
    string reverseWords(string s) {
        if (s.size() == 0) {
            return s;
        }

        removeExtraSpace(s);
        reverse(s.begin(), s.end());

        const int n = s.size();
        string word;

        for (int i = 0; i < n; ++i) {
            if (s[i] == ' ') {
                continue;
            }

            const int left = i;
            while (i < n && s[i] != ' ') {
                word += s[i++];
            }
            reverseWord(s, left, i - 1);
        }

        return s;
    }

private:
    void removeExtraSpace(string& s){
        const int n = s.size();
        int fast = 0, slow = 0;

        // 刪除 s 前面多餘的空格, e.g " hello word"
        while (fast < n && s[fast] == ' ') {
            ++fast;
        }

        // 刪除 s 中間多餘的空格, e.g "hello  word"
        for (; fast < n; ++fast) {
            if (fast > 1 && s[fast - 1] == s[fast] && s[fast] == ' ') {
                continue;
            } else {
                s[slow++] = s[fast];
            }
        }

        // 去掉 string 末尾的空格
        // 檢查最後一個 char, 也就是 s[slow - 1] 是否為 ' ', 若是的話要捨棄
        if (slow > 1 && s[slow - 1] == ' ') {
            s.resize(slow - 1);
        } else {
            s.resize(slow);
        }
    }

    void reverseWord(string& s, int left, int right){
        while (left < right) {
            swap(s[left++], s[right--]);
        }
    }
};
  • time：$O(n)$ ➔ 遍歷 s
  • space：$O(1)$ ➔ in-place, 故只需常數空間