2390. 从字符串中移除星号

🎯 问题描述

描述：
给你一个包含若干星号 * 的字符串 s。
s 中的操作如下：

选择 s 中一颗星号 *。
移除星号 * 左侧最近的那个非星号字符，并移除星号本身。

题目数据保证总会存在可执行的移除操作。
请返回执行完所有操作后的字符串。

说明：

这是一个典型的栈应用问题。
核心策略：
- 我们可以把普通字符看作是“入栈”操作。
- 把星号 * 看作是“出栈”操作（即删除最近加入的字符）。
- 遍历字符串，根据字符类型决定是添加还是删除。
示例：
示例 1：

输入：s = "leet**cod*e"
输出："lecoe"
解释：
- 遇到 'l', 'e', 'e', 't' -> 栈: [l, e, e, t]
- 遇到 '*' -> 删除 't' -> 栈: [l, e, e]
- 遇到 '*' -> 删除 'e' -> 栈: [l, e]
- 遇到 'c', 'o', 'd' -> 栈: [l, e, c, o, d]
- 遇到 '*' -> 删除 'd' -> 栈: [l, e, c, o]
- 遇到 'e' -> 栈: [l, e, c, o, e]
- 结果拼接: "lecoe"

💻 解题思路

思路1：栈模拟

核心逻辑

初始化：
- 创建一个空列表 ans 作为栈，用于存储最终保留下来的字符。
遍历字符串：
- 遍历 s 中的每一个字符 ch。
- 情况 A：星号 *
  - 执行删除操作：弹出栈顶元素 (ans.pop())。
  - 题目保证操作总是可执行，所以不需要检查栈是否为空。
- 情况 B：普通字符
  - 执行添加操作：将字符压入栈 (ans.append(ch))。
构建结果：
- 遍历结束后，将栈中剩余的字符拼接成字符串返回 ("".join(ans))。

代码实现

class Solution:
    def removeStars(self, s: str) -> str:
        ans = []  # 使用列表作为栈
        
        for ch in s:
            if ch == "*":
                # 遇到星号，移除左侧最近的非星号字符（即栈顶元素）
                ans.pop()
            else:
                # 遇到普通字符，加入栈中
                ans.append(ch)
                
        # 将栈中字符拼接成最终字符串
        return "".join(ans)

📊 性能分析

时间复杂度： $O(N)$ $O (N)$
- 其中 $N$ 是字符串 s 的长度。
- 我们只需要遍历一次字符串，每次操作（入栈、出栈）都是 $O(1)$ 。
- 最后的 join 操作也是 $O(N)$ 。
空间复杂度： $O(N)$ $O (N)$
- 我们需要一个栈来存储字符。
- 在最坏情况下（没有星号），栈的大小等于字符串长度。

思考

为什么不用字符串直接修改？
- 在 Python 中，字符串是不可变的。如果使用字符串切片（例如 s = s[:i] + s[i+2:]）来删除字符，每次操作都需要创建一个新的字符串，时间复杂度会达到 $O(N^2)$ ，在数据量大时会超时。
- 使用列表（栈）可以将删除操作优化到 $O(1)$ 。
题目保证的有效性：
- 题目说明“保证总会存在可执行的移除操作”，这意味着当我们遇到 * 时，栈中一定至少有一个字符。因此，代码中不需要写 if ans: 来检查栈是否为空，这简化了代码逻辑。
双指针法（进阶）：
- 这道题也可以用双指针（或者叫“写入指针”）在 $O(1)$ 额外空间（如果不算结果字符串）下解决。
- 思路：维护一个写入指针 j。遍历字符串，如果是普通字符，写入 j 位置并 j++；如果是 *，则 j--（相当于回退写入位置）。
- 虽然双指针空间更优，但栈解法逻辑更直观，且代码更简洁。
类似题目：
- 这道题与 LeetCode 844（比较含退格的字符串）非常相似，都是利用栈来处理“删除前一个字符”的逻辑。掌握这种模式可以解决一类问题。