您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

LeetCode Reverse Words in a String：字符串單詞反轉完整解法

編輯：關於C++

問題描述

給定字符串，按單詞反轉。單詞由非空格字符組成。需處理：首尾空格去除、多空格合併為一。例："the sky is blue" → "blue is sky the"。

雙指針原地算法 (O(1) 空間)

整體反轉字符串
逐個單詞反轉
清理多餘空格（雙指針覆寫）

完整代碼

class Solution {
public:
    void reverseWords(string &s) {
        // 1. 整體反轉
        reverse(s.begin(), s.end());
        // 2. 逐詞反轉 + 3. 清理空格（合併雙指針）
        int n = s.size(), write = 0;
        for (int read = 0; read < n; ) {
            // 跳過空格
            while (read < n && s[read] == ' ') ++read;
            if (read == n) break;
            // 寫入單詞起始位置
            if (write > 0) s[write++] = ' ';
            int start = write;
            // 複製單詞並反轉
            while (read < n && s[read] != ' ') s[write++] = s[read++];
            reverse(s.begin() + start, s.begin() + write);
        }
        s.resize(write); // 截斷多餘尾部
    }
};

關鍵點

整體反轉使單詞順序倒置，但單詞內部也倒置 → 需逐詞再反轉一次
雙指針 `read`/`write` 同時完成「跳過多空格」與「緊湊寫入」
單詞寫入後立即 `reverse` 該區間，無需額外空間
最終 `resize(write)` 截斷殘留字符

標準庫簡易版 (O(n) 空間)

string reverseWords(string s) {
    stringstream ss(s);
    string word, res;
    vector words;
    while (ss >> word) words.push_back(word);
    for (int i = words.size()-1; i >= 0; --i) {
        res += words[i];
        if (i) res += ' ';
    }
    return res;
}