LeetCode 反轉字符串單詞：雙指針原地算法詳解

問題描述

給定字符串 s，按單詞反轉順序。單詞由空格分隔，可能包含多餘空格。輸出單詞間單個空格，首尾無空格。例："the sky is blue" → "blue is sky the"。

C++ 原地算法（O(1) 額外空間）

三步走策略：

1. 整體反轉字符串
2. 逐個單詞反轉
3. 清理多餘空格（雙指針覆蓋）

完整實現

class Solution {
public:
    void reverseWords(string &s) {
        // 1. 整體反轉
        reverse(s.begin(), s.end());
        
        // 2. 逐詞反轉 + 3. 雙指針清理空格
        int n = s.size(), write = 0, read = 0;
        while (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);
    }
};

關鍵細節解析

替代方案：字符串流（簡潔但非 O(1) 空間）

void 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) {
        if (i != words.size()-1) res += ' ';
        res += words[i];
    }
    s = res;
}

Java/Python 內建方法

// Java
s = String.join(" ", Arrays.asList(s.trim().split("\\s+"))).reverse(); // 需自行實現反轉
// 或
List list = Arrays.asList(s.trim().split("\\s+"));
Collections.reverse(list);
s = String.join(" ", list);

# Python 一行解決
s = ' '.join(reversed(s.split()))

複雜度分析

• 原地算法：時間 O(n)，空間 O(1)（不計輸入字符串可修改）
• 輔助數組/流：時間 O(n)，空間 O(n)

避坑指南

• 輸入可能全是空格 → 輸出空字符串
• 單詞間可能多個空格 → 輸出單個
• C++ string::resize 截斷尾部垃圾字符
• 面試若要求 O(1) 空間，必須原地修改字符數組