LeetCode 344. 反轉字符串：雙指針原地交換與語言特性對比

LeetCode 344. 反轉字符串：雙指針原地交換與語言特性對比

題目： 編寫一個函數，輸入字符串，返回反轉後的字符串。要求原地修改輸入字符數組 (LeetCode 實際參數為 char[] s)，空間複雜度 O(1)。

示例： ["h","e","l","l","o"] → ["o","l","l","e","h"]

一、 核心算法：雙指針原地交換 (通用最優解)

邏輯

1. 左指針 left = 0，右指針 right = n - 1。
2. 當 left < right 時，交換 s[left] 和 s[right]。
3. left++, right--，繼續直到相遇或錯過。

Java 實現 (LeetCode 標準簽名)

class Solution {
    public void reverseString(char[] s) {
        int left = 0, right = s.length - 1;
        while (left < right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
            left++;
            right--;
        }
    }
}

C++ 實現 (STL 一行流)

class Solution {
public:
    void reverseString(vector<char>& s) {
        reverse(s.begin(), s.end()); // 
    }
};

Python 實現 (切片/內置)

class Solution:
    def reverseString(self, s: List[str]) -> None:
        s.reverse()        # 列表原地反轉
        # 或 s[:] = s[::-1] # 切片賦值 (原地修改列表內容)

JavaScript 實現

var reverseString = function(s) {
    let l = 0, r = s.length - 1;
    while (l < r) {
        [s[l], s[r]] = [s[r], s[l]]; // 解構賦值交換
        l++; r--;
    }
};

二、 複雜度分析

• 時間： O(n) — 每個字符恰好交換一次 (n/2 次交換)。
• 空間： O(1) — 僅使用常數額外變量 (tmp 或解構暫存)。

三、 字符串 vs 字符數組：關鍵區別

注意：LeetCode 344 參數為 char[] s (或 List[Character])，**專門考察原地修改可變序列**。若輸入為 String，無法原地修改，必須返回新字符串，空間 O(n)。

四、 Java 進階：StringBuilder/StringBuffer 實現原理

// StringBuilder.reverse() 內部實現 (JDK 17+)
public StringBuilder reverse() {
    boolean hasSurrogate = false;
    int n = count - 1;
    for (int i = 0; i < (count >> 1); i++) {
        char c1 = value[i];
        char c2 = value[n - i];
        // 處理代理對 (Supplementary Characters, 4 bytes UTF-16)
        if (Character.isHighSurrogate(c1)) {
            hasSurrogate = true;
        } else if (Character.isLowSurrogate(c2)) {
            hasSurrogate = true;
        }
        value[i] = c2;
        value[n - i] = c1;
    }
    if (hasSurrogate) {
        // 代理對反轉需額外修正順序，防止非法 UTF-16 序列
        // 簡化：重新編碼整個字符串 (較慢但正確)
        // 實際 JDK 實現更精細
    }
    return this;
}

關鍵點： 反轉涉及 **UTF-16 代理對** 時，單純交換 char 會破壞補充字符 (Emoji、罕用漢字)。StringBuilder.reverse() 內部處理了這一邊界情況，而手寫 char[] 交換**不處理代理對**，若輸入含 Emoji 可能產生非法字符序列。LeetCode 344 測試用例通常僅含 BMP 字符 (ASCII/基本多文種平面)，雙指針交換通用正確。

五、 總結與舉一反三

1. 雙指針原地交換 是反轉可變序列的通用最優模板，適用於數組、列表、字符數組。
2. 語言內置庫 (C++ reverse, Python list.reverse, JS 解構交換, Java StringBuilder.reverse) 通常已優化處理邊界 (代理對、迭代器失效)，工程首選。
3. 不可變字符串 反轉必頀 O(n) 空間，面試中需澄清輸入類型與空間要求。
4. 同類題： LeetCode 344 (本題)、LeetCode 541 (反轉字符串 II - 每 2k 反轉前 k)、劍指 Offer 58-II (左旋轉字符串)。

掌握雙指針原地交換模板、理解字符串不可變性與字符數組可變性的工程差異、知曉 UTF-16 代理對反轉陷阱，是基礎算法與字符處理工程化的雙重保障。