2390. Removing Stars From a String

📘 題目敘述

給定一個字串 s，其中包含小寫英文字母與 '*' 字元。

每當遇到一個 '*'，代表要刪除這個 '*' 本身，以及它左邊最近的一個非 '*' 字元。

請回傳所有刪除操作完成後的最終字串。

條件限制

• 1 <= s.length <= 10^5
• s 只包含小寫英文字母與 '*'
• 題目保證：每個 '*' 左邊一定存在可以被刪除的字元

🧠 解題思路（一）建立stack

這題的關鍵在於：

'*' 只會影響「它左邊最近還存在的字元」

這個行為非常符合 Stack（堆疊） 的特性：

• 一般字母 → 先進後出地暫存
• 遇到 '*' → 刪掉最近放進來的字元

所以我的想法是：

• 從左到右掃描字串
• 用 stack 存目前「還沒被刪掉的字元」
• 普通字母就 push
• 遇到 '*' 就 pop 一個字元

最後 stack 裡剩下的字元，就是刪除完成後的結果。

所有變數

• ans：stack<char> 用來存目前還有效（未被刪除）的字元
• a：for-each 迴圈中，當前讀到的字元
• ns：最後輸出的結果字串，用來把 stack 內容組回字串

🪜 主要流程步驟

第一步：從左到右掃描字串

我用 for (char a : s) 逐字處理：

情況一：a 是一般字母

• 代表目前這個字元還沒被任何 '*' 刪掉
• 直接 push 進 stack

ans.push(a);

情況二：a == '*'

• 根據題目規則：
  • 這個 '*' 會刪掉「左邊最近的一個字元」
• 而那個「最近的字元」正好就是 stack 的 top
• 所以直接 pop()

ans.pop();

第二步：把 stack 內容轉回字串

stack 的特性是：

• 後放進去的字元在上面
• 但題目要的是「原本從左到右的順序」

所以我分兩個小步驟：

1. 先把 stack 內容依序 pop 出來，放進字串 ns
   • 這時順序是反的
2. 再把 ns 整個 reverse

第三步：回傳結果

• ns 就是所有 '*' 操作完成後的最終字串
• 直接回傳

💡 為什麼 Stack 是最自然的解法？

• '*' 永遠只影響「最近的一個字元」
• 這正是 LIFO（Last In First Out）
• 不需要回頭掃描、不需要額外紀錄索引
• 每個字元只處理一次 → O(n)

💻 程式碼實作（一）

class Solution {
public:
    string removeStars(string s) {
        stack<char> ans;
        for (char a : s) {
            if (a == '*') {
                ans.pop();
            } else {
                ans.push(a);
            }
        }
        string ns = "";
        while (!ans.empty()) {
            ns.push_back(ans.top());
            ans.pop();
        }
        reverse(ns.begin(), ns.end());
        return ns;
    }
};

🧠 解題思路（二）用string當stack

這題的本質是：

每遇到一個 '*'，就刪掉「最近加入的字元」

這完全符合 Stack（後進先出, LIFO） 的行為。

但我發現一件事：

• 我只會在「字串尾端」加入字元
• 也只會在「字串尾端」刪除字元

所以其實 不需要真的用 stack<char>，

直接用 string 本身當作 stack 就可以。

所有變數

主要變數

• ans：
  • 型態是 string
  • 用來當作「模擬 stack 的容器」
  • 永遠只對尾端進行 push_back / pop_back

🪜 主要流程步驟

第一步：初始化結果字串

• 建立一個空的 string ans
• 這個字串會動態維護「目前有效的字元結果」

第二步：從左到右掃描字串 s

對於每一個字元 a：

情況一：a 不是 '*'

• 代表是一般字元
• 直接加到結果尾端

ans.push_back(a);

情況二：a == '*'

• 代表要刪除「最近加入的字元」
• 因為題目保證一定存在
• 直接刪掉結果字串尾端即可

ans.pop_back();

第三步：回傳結果

• 所有字元處理完成後
• ans 本身就是最終字串
• 不需要再反轉或額外處理

💡 為什麼 string 可以當作 stack？

因為：

• push_back() = stack 的 push()
• pop_back() = stack 的 pop()
• 而且都是 O(1) 操作

這題只需要「尾端操作」，

所以 string 本身就已經是最適合的資料結構。

💻 程式碼實作（二）

class Solution {
public:
    string removeStars(string s) {
        string ans;
        for (char a : s) {
            if (a == '*') {
                ans.pop_back();
            } else {
                ans.push_back(a);
            }
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/removing-stars-from-a-string/