Removing Stars From a String

題目描述

給定包含星號 * 的字串 s。每次操作移除最靠近星號左邊的非星號字元，以及星號本身。回傳移除所有星號後的結果。

輸入：s = "leet**cod*e"
輸出："lecoe"

輸入：s = "erase*****"
輸出：""

解題思路

初始化 Stack

建立空的 Stack（或用陣列模擬），用來追蹤目前「還活著」的字元

遍歷字串

for 迴圈從左到右逐字元掃描字串 s

普通字元

若當前字元不是 *，push 進 Stack。例如遇到 l,e,e,t 依序推入

星號

若當前字元是 *，呼叫 stack.pop() 彈出最上面的字元（等同退格刪除）

組合結果

遍歷結束後，Stack 中剩餘字元從底到頂就是答案。用 join 拼接成字串

程式碼

C#

csharp

public class Solution {
    public string RemoveStars(string s) {
        var stack = new Stack<char>();
        foreach (char c in s) {
            if (c == '*')
                stack.Pop();   // 刪除前一個字元
            else
                stack.Push(c); // 保留字元
        }
        // Stack 是後進先出，需要反轉
        var arr = stack.ToArray();
        Array.Reverse(arr);
        return new string(arr);
    }
}

TypeScript

typescript

function removeStars(s: string): string {
    const stack: string[] = [];
    for (const c of s) {
        if (c === "*") stack.pop();
        else stack.push(c);
    }
    return stack.join("");
}

Python

python

def removeStars(s: str) -> str:
    stack = []
    for c in s:
        if c == "*":
            stack.pop()
        else:
            stack.append(c)
    return "".join(stack)

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(n) |

每個字元最多被 push 一次和 pop 一次，總操作數 ≤ 2n，因此時間 O(n)。Stack 最大深度等於最終結果長度，最壞為 n（無星號時），空間 O(n)。

邊界情況

沒有星號：例如 "abc"，所有字元依序 push，結果就是原字串
星號在開頭：題目保證星號左邊一定有非星號字元可刪，所以不會出現 "*abc" 這種無效輸入
全部被刪除：例如 "ab**"，兩個字元被兩個星號依序刪掉，Stack 為空，回傳空字串

圖解

s = leet**cod*e

l,e,e,t→

push l,e,e,t

*,*→

pop t, pop e (兩個*)

c,o,d→

push c,o,d

*→

pop d (一個*)

e→

push e

join→

stack: [l,e,c,o,e] → lecoe

圖表展示 Stack 的操作過程：先推入 l,e,e,t，遇到兩個星號依序彈出 t 和 e。再推入 c,o,d，一個星號彈出 d。最後推入 e，Stack 剩 [l,e,c,o,e] 即為答案。

進階觀點

💡面試追問

Q: 能否不用 Stack？ A: 可以用一個 write 指針在字元陣列上原地操作。遇到普通字元寫入 arr[write++]，遇到星號就 write--。最後取 arr[0..write-1]。原理跟 Stack 相同，但省去 Stack 的額外結構開銷。
Q: C# 為什麼要 Reverse？ A: C# 的 Stack<T>.ToArray() 是從頂端開始輸出（後進先出），所以順序是反的。改用 List<char> 模擬 Stack（用 Add 和 RemoveAt(Count-1)）可以避免反轉，join 時順序就是正確的。
Q: 如果星號可以刪除多個字元呢？ A: 那需要數字+星號的格式（例如 "abc3*" 代表刪 3 個字元），遇到星號時先解析前面的數字 k，再 pop k 次。需要額外處理數字的解析邏輯。

理解測驗

🤔 為什麼 Stack 適合這題？

🤔 s = "abc" （沒有星號）的結果是什麼？