LeetCode 题解工作台
从字符串中移除星号
给你一个包含若干星号 * 的字符串 s 。 在一步操作中，你可以： 选中 s 中的一个星号。 移除星号 左侧 最近的那个 非星号 字符，并移除该星号自身。 返回移除 所有 星号之后的字符串 。 注意： 生成的输入保证总是可以执行题面中描述的操作。 可以证明结果字符串是唯一的。 示例 1： 输入： s…
3
题型
7
代码语言
3
相关题
当前训练重点
中等 · 栈·状态
答案摘要
我们可以使用栈模拟操作过程。遍历字符串 ，如果当前字符不是星号，则将其入栈；如果当前字符是星号，则将栈顶元素出栈。 最后我们将栈中元素拼接成字符串返回即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
给你一个包含若干星号 * 的字符串 s 。
在一步操作中，你可以：
- 选中
s中的一个星号。 - 移除星号 左侧 最近的那个 非星号 字符，并移除该星号自身。
返回移除 所有 星号之后的字符串。
注意：
- 生成的输入保证总是可以执行题面中描述的操作。
- 可以证明结果字符串是唯一的。
示例 1：
输入：s = "leet**cod*e" 输出："lecoe" 解释：从左到右执行移除操作： - 距离第 1 个星号最近的字符是 "leet**cod*e" 中的 't' ，s 变为 "lee*cod*e" 。 - 距离第 2 个星号最近的字符是 "lee*cod*e" 中的 'e' ，s 变为 "lecod*e" 。 - 距离第 3 个星号最近的字符是 "lecod*e" 中的 'd' ，s 变为 "lecoe" 。 不存在其他星号，返回 "lecoe" 。
示例 2：
输入：s = "erase*****" 输出："" 解释：整个字符串都会被移除，所以返回空字符串。
提示：
1 <= s.length <= 105s由小写英文字母和星号*组成s可以执行上述操作
解题思路
方法一：栈模拟
我们可以使用栈模拟操作过程。遍历字符串 ，如果当前字符不是星号，则将其入栈；如果当前字符是星号，则将栈顶元素出栈。
最后我们将栈中元素拼接成字符串返回即可。
时间复杂度 ，其中 是字符串 的长度。忽略答案字符串的空间消耗，空间复杂度 。
class Solution:
def removeStars(self, s: str) -> str:
ans = []
for c in s:
if c == '*':
ans.pop()
else:
ans.append(c)
return ''.join(ans)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the candidate's understanding of stack-based state management.
- question_mark
Check if they optimize space and time complexity using the stack pattern.
- question_mark
Ask them to explain the stack's role in the problem-solving process.
常见陷阱
外企场景- error
Forgetting to pop the stack when encountering a star, leading to incorrect results.
- error
Misunderstanding the traversal order and removing characters from the wrong position.
- error
Assuming the string might be empty after removals, which could lead to incorrect handling.
进阶变体
外企场景- arrow_right_alt
Modify the problem to handle uppercase letters as well.
- arrow_right_alt
Introduce multiple stars consecutively, testing how the solution handles continuous removals.
- arrow_right_alt
Change the approach to use an array instead of a stack, observing the trade-offs in space and time.