解題說明
Removing Stars From a String
題目描述:給定字串 s,其中包含字母和星號 '*'。每個 '*' 操作:移除它左邊最近的一個非 '*' 字元,以及 '*' 本身。重複執行直到所有 '*' 都被移除,回傳最終字串。題目保證操作總是合法的(不會在空字串上執行)。
解題思路:使用堆疊(stack)模擬:遍歷字串中的每個字元,若是普通字母則 push 到堆疊;若是 '*' 則 pop 堆疊頂端(移除最近的非星號字元)。遍歷完成後,堆疊中由下到上的元素就是最終字串,將其組合回傳即可。此解法 O(n) 時間、O(n) 空間,最為直觀。
C++ 解法
複雜度分析
時間複雜度:O(n) — 每個字元恰好被 push 和 pop 各最多一次。
空間複雜度:O(n) — 堆疊(字串)最多儲存 n 個字元。
虛擬碼
1. Initialize empty stack (string) 2. For each character c in s: a. If c == '*': pop_back() from stack b. Else: push_back(c) to stack 3. Return stack as result string
其他解法
雙指標(原地模擬):用一個指標 write 模擬堆疊頂,讀取字元時若非 '*' 則 s[write++] = c,若是 '*' 則 write--。最後回傳 s.substr(0, write)。可避免額外字串分配,但會修改輸入。
計數法(特殊情況):若 '*' 只出現在字串末尾(非本題),可用簡單計數。但本題星號可出現在任意位置,必須追蹤位置資訊,堆疊是最合適的資料結構。
延伸思考
- 若一個
'*'需要移除左邊最近的「母音字母」而非任意字母,堆疊策略需要如何調整? - 若允許
'*'出現在字串開頭(此時操作非法),如何在保持 O(n) 的前提下偵測並回傳錯誤? - 如何修改解法,使其同時支援
'?'字元(移除右邊最近的非星非問號字元)?