LeetCode 2390. 从字符串中移除星号
题目描述
题意分析
字符串由小写字母和星号组成。每次遇到一个星号，要同时删除这个星号与它左侧最近的、尚未被删除的字母，直到所有星号都被移除，返回剩余字母组成的字符串。
最近字母由此前的删除结果决定，不一定是原字符串中紧挨星号的位置。题目保证删除总能进行且最终结果唯一，因此可以按从左到右的顺序处理，也无需另行定义无法删除时的行为。
解法：用栈保存尚未删除的字母
核心思路
[!blue]
从左到右扫描时，已经处理完的前缀只需保留仍然存在的字母。下一个星号要删除的恰好是这个存活序列的末尾，也就是最近加入且尚未删除的字母，符合栈的后进先出顺序。
用可增长缓冲区的末尾充当栈顶。读到字母就追加，读到星号就删除末尾一个字母，星号自身不写入。连续星号会逐次向更早的存活字母回退，历史上已删除的位置不会再次参与。
每次处理后，缓冲区都恰好等于当前前缀完成所有星号操作后的结果；新字母与新星号的两种更新都保持这个性质。因此扫描结束，缓冲区就是完整答案，不需要重新在原串中搜索或搬移后面的字符。
缓冲区从头到尾保存的就是剩余字母的原顺序，返回时直接转换为字符串，不能再反转。即使最后全部删除，空缓冲区也自然得到空结果。
解题步骤
- 创建空缓冲区，末尾作为栈顶。
- 从左到右读取每个字符，普通字母直接追加。
- 星号触发删除末尾一位，星号自身不保留。
- 全部字符处理后，按缓冲区当前顺序返回结果。
代码实现
class Solution {
public String removeStars(String s) {
// StringBuilder 的尾部就是栈顶：追加即压栈，删末位即弹栈。
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '*') {
// 星号消掉当前存活序列的末尾，自己不入栈。
sb.deleteCharAt(sb.length() - 1);
} else {
sb.append(c);
}
}
// 自底向上就是答案顺序，无需反转。
return sb.toString();
}
}
func removeStars(s string) string {
// 字节切片的尾部就是栈顶：append 即压栈，截断即弹栈。
stack := make([]byte, 0, len(s))
for i := 0; i < len(s); i++ {
if s[i] == '*' {
// 星号消掉当前存活序列的末尾，自己不入栈。
stack = stack[:len(stack)-1]
} else {
stack = append(stack, s[i])
}
}
// 自底向上就是答案顺序，无需反转。
return string(stack)
}
复杂度分析
- 时间复杂度：$O(n)$，每个字符只读取一次，每个字母最多入栈一次、被删除一次。
- 空间复杂度：$O(n)$，保存仍存活的字母；最终结果很短也不代表过程中缓冲区一直很短。
关键点总结
[!green]
- 栈保存已经处理前缀中的存活字母，栈顶正是星号要删除的最近字母。
- 星号只触发一次弹出，不作为普通字符入栈。
- 输入保证操作合法，按从左到右处理时可以直接删除栈顶。
- 输出顺序已经保存在缓冲区中，不需要反转。
易错点总结
[!yellow]
- 直接删除原下标前一位会忽略此前操作，无法处理连续星号造成的回退。
- 删除字母后又把星号追加进结果，会保留本该一起移除的字符。
- 将栈按弹出顺序组装答案会反转剩余字母的顺序，应直接读取缓冲区。
- 题目保证合法操作，不应擅自把非法空栈删除解释为忽略星号。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 844. 比较含退格的字符串 | 简单 | 同样把特殊字符当作退格操作，原题比较两串结果，本题直接返回处理后的字符串。 |
| 1047. 删除字符串中的所有相邻重复项 | 简单 | 同样用栈删除相邻内容，原题由相同字母触发，本题由显式星号触发。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！