LeetCode：Reverse Words in a String 字符串單詞反轉

問題描述

給定一個字符串，以單詞為單位反轉順序。單詞由非空格字符組成，單詞間可能有多個空格，結果中單詞間僅保留一個空格，且首尾無空格。例如 "i am echo" → "echo am i"。

解法一：使用 vector 收集單詞再反轉

遍歷字符串，提取單詞存入 vector，然後反轉 vector，最後用單個空格拼接。

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

解法二：使用棧（先進後出）

提取單詞直接壓入棧，然後彈出拼接，省去反轉步驟。

class Solution {
public:
    void reverseWords(string &s) {
        stack st;
        int n = s.size(), i = 0;
        while (i < n) {
            while (i < n && s[i] == ' ') ++i;
            if (i >= n) break;
            int j = i;
            while (j < n && s[j] != ' ') ++j;
            st.push(s.substr(i, j - i));
            i = j;
        }
        s.clear();
        while (!st.empty()) {
            s += st.top(); st.pop();
            if (!st.empty()) s += ' ';
        }
    }
};

複雜度分析

• 時間複雜度：O(n)，單次遍歷。
• 空間複雜度：O(n)，存儲所有單詞。

總結

本題關鍵在於正確處理多餘空格與邊界情況。兩種方法思路清晰，vector 反轉更直觀，棧方法略顯優雅。實際面試中任選其一均可。