解題說明
Reverse String
題目描述:
給定一個字元陣列 s,原地(in-place)反轉它。必須使用 O(1) 額外空間。
解題思路:
使用雙指標法。設定兩個指標 left 和 right 分別指向陣列的首尾:
- 交換
s[left]和s[right]。 left向右移,right向左移。- 重複直到
left >= right。
每次交換將一對對稱位置的字元歸位,遍歷一半陣列即完成反轉。
C++ 解法
複雜度分析
時間複雜度:O(n) — 雙指標各走 n/2 步,共執行 n/2 次交換。
空間複雜度:O(1) — 只使用兩個指標變數,原地修改。
虛擬碼
1. Initialize left = 0, right = length - 1 2. While left < right: a. Swap s[left] and s[right] b. left++, right-- 3. Done (array is reversed in-place)
其他解法
遞迴法:reverse(s, left, right) 交換首尾後遞迴 reverse(s, left+1, right-1)。時間 O(n),空間 O(n) 遞迴深度。簡潔但遞迴堆疊消耗 O(n) 空間,不滿足 O(1) 空間要求。
使用 STL:直接呼叫 std::reverse(s.begin(), s.end())。面試中通常要求手動實作,但工程上這是最佳選擇。底層實作即為雙指標交換。
延伸思考
- 若要反轉字串中的單詞順序而非字元順序,如何解?(LeetCode 151)
- 若只反轉母音字母的位置,其餘字元不動,如何修改雙指標法?(LeetCode 345)
- 此雙指標技巧還可應用在哪些「原地」操作的問題上?(如判斷回文、移除元素等)