解題說明
Remove All Adjacent Duplicates in String II
題目描述:
給定字串 s 和整數 k,反覆移除字串中 k 個連續相同字元的片段,直到無法再移除為止,回傳最終字串。
解題思路:
使用堆疊(stack),每個元素存放一對 (字元, 連續計數)。遍歷字串時,若當前字元與堆疊頂端相同,則計數加一;否則壓入新元素,計數設為 1。當頂端計數達到 k 時,彈出該元素(等同刪除 k 個連續字元)。遍歷結束後,將堆疊中的元素依序展開還原成字串即為答案。此方法只需一次遍歷,避免了反覆掃描字串的低效做法。
C++ 解法
複雜度分析
時間複雜度:O(n) — 每個字元最多被壓入和彈出堆疊各一次。
空間複雜度:O(n) — 堆疊最多存放 n 個元素。
虛擬碼
1. Initialize an empty stack of (char, count) pairs
2. For each character c in s:
a. If stack is not empty and top character == c:
- Increment top count
- If top count == k, pop the top element
b. Else push (c, 1) onto stack
3. Build result string by expanding each (char, count) pair
4. Return result其他解法
雙指標法 O(n):用一個慢指標寫回結果,搭配計數陣列追蹤每個位置的連續長度。當計數達到 k 時,慢指標回退 k 步。空間 O(n) 用於計數陣列,但可原地修改字串。
暴力模擬 O(n²/k):反覆掃描字串,每次找到並刪除 k 個連續字元。簡單直觀但效率差,最壞情況下需要 O(n/k) 輪掃描。
延伸思考
- 若 k = 2,有沒有更簡潔的實作方式?(即 LeetCode 1047 的變體)
- 若要求回傳刪除的順序或次數,如何修改演算法?
- 若字串非常長且為串流輸入(streaming),堆疊法是否仍然適用?