LeetCode 2390. 从字符串中移除星号

约 9 分钟
文章信息 3 个分类 3 个标签
分类
LeetCode 中等 LeetCode 75
标签
字符串 栈 模拟
目录

题目描述

✅ 2390. 从字符串中移除星号

题意分析

给一个由小写字母和星号组成的字符串。每一步可以挑一个星号，把它左边最近的那个非星号字符和它自己一起删掉。反复操作直到没有星号，返回最终的字符串。题目保证输入总是可以执行完，也保证结果唯一。

「左边最近的非星号字符」这句话要拆开看。一是方向：只往左看，右边的字符与这个星号无关。二是距离：取最近的那个，也就是删掉的永远是「当前还活着的字符里位置最靠右的那个」。三是限定：跳过其他星号，因为星号自己不是被删的对象。三点合起来说的其实是同一件事 —— 每个星号消掉的都是当前存活序列的末尾字符。

「结果唯一」这个保证很关键，它意味着不必纠结操作顺序。虽然题面允许任意挑一个星号来操作，但无论从哪个星号开始，最终结果都一样，所以可以放心地从左到右按顺序处理，这是把题目从「搜索」降格为「一次扫描」的许可证。

官方样例 "leet**cod*e" → "lecoe" 值得逐步核对：第一个星号消掉 t，第二个星号消掉此时的末尾 e（注意不是 l 也不是原串里的其他 e），第三个星号消掉 d，剩下 l、e、c、o、e。"erase*****" → "" 则说明结果可以是空串，而且五个星号恰好把五个字母全部消掉，删除是严格一对一的。

约束是 1 <= s.length <= 10^5，且保证操作合法。前者说明必须做到线性或接近线性，任何「每次删除都重建一遍字符串」的写法都会退化成平方级；后者说明不会出现「星号左边已经没有字符」的情况，收尾时不需要防御性判空，但写代码时最好清楚这份安全感的来源。

解法：用栈模拟消除

核心思路

先想暴力：每遇到一个星号，就回头在已处理的部分里往左找第一个还活着的字符，把两者标记为删除。这需要为每个星号做一次可能很长的回溯，最坏是 $O(n^2)$；用字符串拼接来「删掉最后一个字符」更糟，因为每次 substring 都会复制整段内容。

瓶颈在于反复地寻找和搬运「末尾」。但仔细看操作的性质：星号总是消掉当前存活序列的最后一个字符，而后来的字符总是追加在末尾 —— 这是标准的后进先出：最晚进来的字符最先被消掉。既然如此，就不该用「回头找」的方式访问末尾，而应该用一个天然把末尾放在手边的结构。

于是维护一个栈，从左到右扫一遍原串，不变量是：扫描到位置 i 时，栈里自底向上恰好是前缀 s[0..i] 经过全部消除操作后剩下的字符，顺序与它们在原串中的先后一致。遇到字母就压栈（它成为新的末尾，也是下一个星号的候选受害者）；遇到星号就弹栈（消掉当前末尾）。扫描结束时栈里从底到顶就是答案。

这条不变量为什么成立？归纳来看，加入一个字母只是把新末尾接上去，前缀的消除结果显然照旧；加入一个星号则要消掉「前缀消除结果的末尾」，而按不变量那正是栈顶。星号自身不入栈，因为它已经在弹栈的瞬间履行完职责。至于「结果唯一」的保证，正是它允许我们把星号严格按从左到右的顺序结算，而不必考虑先算右边的星号会不会影响左边。

实现上没必要真的用 Stack 或 Deque：可变字符串（Java 的 StringBuilder、Go 的字节切片）本身就是一个栈 —— 尾部追加相当于压栈，把长度减一相当于弹栈，两者都是均摊 $O(1)$，而且扫描结束时它的内容已经是正确顺序的答案，不需要任何反转或重排。若用 Deque 的头插法模拟栈，最后还得把元素倒出来再翻转一次，白白多一步、也多一次出错机会。

解题步骤

  • 准备一个可变字符串（或字节切片）当作栈，容量按原串长度预留。为什么：它的尾部就是栈顶，追加与截断都是均摊常数时间，且天然保持从左到右的顺序，省掉收尾的反转。
  • 从左到右逐个字符扫描原串。为什么：题目保证结果唯一，因此星号可以按出现顺序依次结算，一趟扫描就够，不需要回溯或多轮迭代。
  • 遇到非星号字符，追加到栈尾。为什么：它成为当前存活序列的新末尾，也就是下一个星号会消掉的那个，这正是「左边最近的非星号字符」的含义。
  • 遇到星号，把栈尾的一个字符删掉，星号自己不入栈。为什么：星号的作用就是消掉当前末尾，消完它就不再有任何影响；若把星号也压进去，它会被后来的星号误当成字母删掉。
  • 扫描结束后，把栈中内容按自底向上的顺序拼成字符串返回。为什么：不变量保证此时栈里就是完整前缀（也就是整个串）消除后的结果，顺序已经正确，直接输出即可。

以 "leet**cod*e" 走一遍：栈初始为空。

读 l、e、e、t，依次入栈，栈内为 l e e t。读到第一个 *，弹出栈顶 t，栈内为 l e e —— 与题面描述的「第 1 个星号最近的字符是 t」一致。读到第二个 *，弹出当前栈顶 e（原串下标 2 的那个），栈内为 l e；注意这一步删的是当时的末尾，而不是原串里星号左边紧挨着的那个字符，两者恰好因为前一次删除而不同。

继续读 c、o、d 入栈，栈内为 l e c o d。读到第三个 *，弹出 d，栈内为 l e c o。最后读 e 入栈，栈内为 l e c o e。扫描结束，拼接得到 "lecoe"，与期望一致。

"erase*****" 边界：先把 e、r、a、s、e 全部入栈，栈内五个字符；随后五个星号逐个弹栈，栈依次变成四、三、二、一、零个元素。扫描结束栈为空，返回空串。这里也能看出题目「保证可执行」的含义 —— 星号的数量恰好不超过它左侧存活字符的数量，所以每次弹栈都有东西可弹。

代码实现

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)$，每个字符被扫描一次；字母至多入栈一次、出栈一次，星号只触发一次弹栈，追加与截断都是均摊常数时间，因此总操作次数与 $n$ 同阶，不存在任何回溯或重扫。
  • 空间复杂度：$O(n)$，栈最坏要装下全部字母（输入中一个星号都没有时），这也是返回值本身占用的空间；除此之外只有一个下标变量，没有额外容器。

关键点总结

  • 「只对最近的一个元素生效」的操作，本质就是栈。识别信号是「最近」「最后一个」「向左找第一个」这类措辞，一旦出现就该想到后进先出，而不是去写回溯查找。
  • 可变字符串就是现成的栈，且顺序天然正确。尾部追加与截断长度分别对应压栈与弹栈，扫描结束直接输出即可；用 Deque 头插法模拟栈虽然也对，但收尾必须反转，平白多一步易错点。
  • 「结果唯一」的保证换来了「按顺序一趟处理」的许可。这类保证不是废话，它决定了能否把「任意顺序操作」的题目降格成一次线性扫描 —— 读题时看到这种句子要专门记一笔。
  • 触发删除的字符自己不入栈。星号的全部作用在弹栈那一刻结算完毕，若把它也压进去，后续的星号会把它当成普通字符删掉，答案会莫名其妙地多出星号或少删字母。
  • 面试视角：这题写完最常见的追问是「能不能不用额外空间」。可以答：如果允许原地修改字符数组，用一个写指针 top 表示栈顶位置、读指针遍历全串，遇字母写入 arr[top++]、遇星号执行 top--，最后取前 top 个字符即可，额外空间降到 $O(1)$（不计返回值）—— 这其实是同一个栈，只是把它铺在了原数组上。第二个追问通常是「星号左边没有字符怎么办」，正确回答是「题目保证不会发生，但真要防御就在弹栈前判空」，而不是含糊带过。

易错点总结

  • 遇到星号只跳过、忘了删除："leet**cod*e" → 输出 "leetcode"，"erase*****" → 输出 "erase"。等于把题目做成了「过滤掉所有星号」，看起来能跑、结果却完全不对。
  • 用 Deque 模拟栈后直接依次弹出拼接："leet**cod*e" → 输出 "eocel"，正好是正确答案的倒序。栈的弹出顺序是从顶到底，与字符串的书写顺序相反，用这类容器就必须记得最后反转一次。
  • 收尾时多做了一次反转：与上一条同果，"leet**cod*e" → 输出 "eocel"。用可变字符串当栈时内容已经是正序，画蛇添足地调一次反转反而把答案弄反了。判断依据很简单：容器的「尾」是不是栈顶。
  • 一个星号删两个字符："leet**cod*e" → 输出 "ce"，而正确答案是 "lecoe"。误以为「移除星号自身」也要从结果串里扣一个字符，其实星号根本没进过栈，不需要额外扣除。
  • 把星号也压进栈：后面的星号会把前面的星号当作普通字符弹掉，导致该删的字母没删。"leet**cod*e" 会剩下 t 或 e 之类本该消失的字符，输出多出一到两个字母。触发操作的符号绝不入栈，这是栈类模拟题的通则。
  • 用字符串拼接加 substring 来模拟删除：结果正确，但每次删除都要复制整段内容，最坏退化到 $O(n^2)$；10^5 长度、星号密集的数据会直接超时。删除末尾必须是常数时间的操作，这决定了容器的选择。
  • 用 replaceAll 之类的正则反复消除：例如反复把「字母 + 星号」替换成空串直到不再变化。逻辑上能收敛到正确答案，但每轮扫描整串、最坏要迭代 $O(n)$ 轮，同样是平方级；而且正则在超长字符串上的常数极大，实测比朴素拼接还慢。
  • 弹栈前不判空却又改了输入假设：本题保证合法所以无需判空，但如果把这段代码复用到不保证合法的场景（比如输入以星号开头），sb.length() - 1 会取到 -1 并抛出下标越界异常。搬运代码时要连同它依赖的前提一起搬。
  • 在 Java 里用 s.charAt(i) 之外的方式逐字符取值时忽略了字符类型：把字符与 '*' 比较写成与字符串 "*" 比较会编译失败，改用 equals 又要先装箱成 String，白白增加开销。逐字符处理时统一用 char 与字符字面量比较最省事。

相似题目

题目 难度 考察点
1047. 删除字符串中的所有相邻重复项 简单 同样用栈消除，但触发条件是「与栈顶相同」而非遇到特定符号，需要先看栈顶再决定压还是弹
1544. 整理字符串 简单 消除条件变成「与栈顶大小写互异」，同样是压栈前先比对，考察触发条件的判断而非位置
20. 有效的括号 简单 弹栈时必须校验栈顶是否匹配、且可能栈空，返回的是合法性而不是剩余内容
71. 简化路径 中等 栈里存的是路径片段而非单个字符，.. 相当于本题的星号，还要额外处理空片段与结尾斜杠
735. 小行星碰撞 中等 一次入栈可能连续弹出多个元素，甚至新元素自己被消灭，比本题固定「一星号消一字符」复杂得多