LeetCode 1003. 检查替换后的词是否有效

约 5 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 猿辅导
标签
字符串 栈
目录

题目描述

✅ 1003. 检查替换后的词是否有效

题意分析

从空串出发，每次可以往当前串的任意位置插入一个完整的 abc，问给定的 s 能不能这样造出来。

「往任意位置插入」是正向定义，直接顺着它搜索会爆炸：长度 n 的串需要 n/3 次插入，每次有若干个可选位置，方案数是阶乘量级。所以第一步必须把它反过来读——s 有效，当且仅当反复从 s 里删掉某个连续的 abc 子串，最终能把整个串删空。删除是插入的逆操作，两个方向的可达性完全等价。

反向之后仍有一个疑问：s 里可能同时存在多个 abc，先删哪一个会不会影响最终结果？答案是不会。删掉一个 abc 只会让它左右两侧变成相邻，不可能破坏别处已经成型的 abc（那三个字符要么整体在左侧、要么整体在右侧，不会被拆开）。既然任意删除顺序殊途同归，就可以固定成「从左往右扫，一旦凑出 abc 立刻删」这种最方便实现的顺序，不需要回溯。

约束给的信号：s 只含 a、b、c 三种字符，长度上限 $2 \times 10^4$，暗示线性或近线性做法即可，同时也提醒答案必须是「一次扫描 + 一个后进先出的暂存结构」这种形态——因为每次删除影响的是最近那几个字符。

边界：空串按定义有效（不过题目保证 s 非空）；长度不是 3 的倍数一定无效，这一点会被主逻辑自然覆盖，不必单独判；开头字符不是 a 也一定无效，同样会被自然覆盖。

解法：栈模拟消除

核心思路

把构造过程反过来看：插入一个 abc 的逆操作，就是删除一个连续的 abc。因此，原串有效当且仅当它能通过反复删除 abc 变成空串。

直接在字符串中反复查找、删除会产生重复扫描和搬移。更合适的做法是从左到右扫描，用栈保存当前前缀消除后的残留串。每压入一个字符，只检查栈顶三个字符；若为 abc，就立即弹出。

不变量：处理完前 i 个字符后，栈自底向上的内容，正是前缀 s[0..i) 充分消除 abc 后的残留串，并且栈内不再含有 abc。

不变量成立的原因是：加入新字符前，栈内已经无法继续消除；加入后若出现新的 abc，它只能以新字符结尾，所以只可能位于栈顶。删除这三个字符后，剩余部分是旧栈的一个前缀，仍然无法继续消除，一次检查就足够。

正确性还要覆盖两个方向。若在 x 与 y 之间插入一个完整的 abc，栈处理完 xabc 后与处理完 x 的状态相同，继续处理 y 的结果也相同；所以从空串经过任意次插入得到的字符串最终一定栈空。反过来，栈空时每次弹栈都对应一次合法删除，反向执行这些删除就得到一条从空串构造原串的插入序列。因此，栈空与字符串有效等价。

解题步骤

  1. 准备一个最多容纳 s.length() 个字符的栈，并用 top 表示栈中元素个数。
  2. 依次把当前字符压栈。
  3. 若栈中至少有 3 个字符，且栈顶向前的三个字符依次为 a、b、c，令 top -= 3 完成消除。
  4. 扫描结束后返回 top == 0。

例如 aabcbc 的栈变化为：

a -> aa -> aab -> aabc -> a -> ab -> abc -> 空

最后栈空，因此有效。反例 abccba 在消除开头的 abc 后还剩 cba，无法继续消除，因此无效。

长度不是 3 的倍数、首字符不是 a、末尾留下不完整片段等情况，都会自然表现为栈非空，无需额外分支。

代码实现

class Solution {
    public boolean isValid(String s) {
        char[] stack = new char[s.length()];
        int top = 0;

        for (int i = 0; i < s.length(); i++) {
            stack[top++] = s.charAt(i);
            if (top >= 3
                    && stack[top - 3] == 'a'
                    && stack[top - 2] == 'b'
                    && stack[top - 1] == 'c') {
                top -= 3;
            }
        }
        return top == 0;
    }
}

func isValid(s string) bool {
	stack := make([]byte, 0, len(s))
	for i := 0; i < len(s); i++ {
		stack = append(stack, s[i])
		n := len(stack)
		if n >= 3 && stack[n-3] == 'a' && stack[n-2] == 'b' && stack[n-1] == 'c' {
			stack = stack[:n-3]
		}
	}
	return len(stack) == 0
}

复杂度分析

  • 时间复杂度： $O(n)$。每个字符入栈一次，匹配和弹栈都是常数操作。
  • 空间复杂度： $O(n)$。无可消除子串时，栈最多保存全部字符。

关键点总结

  • 将“反复插入”转化为等价的“反复删除”，避免枚举插入位置。
  • 栈保存的是当前前缀的不可消除残留，这是理解算法和证明正确性的核心不变量。
  • 新的可消除子串必然出现在栈顶，因此每次入栈后只需检查最后三个字符。
  • 用字符数组模拟栈可避免 Java 中 Character 装箱，逻辑也与 Go 切片版本一致。

易错点总结

  • 把匹配方向写反： 栈顶是 c，次顶是 b，第三个才是 a。abccba 可暴露把 cba 错当成可消除串的问题。
  • 只比较字符数量： aaabbbccc 中三种字符数量相同，但不存在可连续消除的 abc，答案是 false。
  • 在原字符串上循环 replace： 结果可能正确，但每轮都要重新扫描和构造字符串，最坏会退化为 $O(n^2)$。
  • 用消除次数作为答案： abcab 虽能消除一次，但仍残留 ab；最终判据必须是栈是否为空。

相似题目

题目 难度 考察点
1047. 删除字符串中的所有相邻重复项 简单 消除的模式是「相邻两个相同字符」，只需比对栈顶一个元素，是本题的最简形态
1209. 删除字符串中的所有相邻重复项 II 中等 消除长度变成任意 k，栈里要额外存计数，不能再靠固定长度比对
20. 有效的括号 简单 消除的是配对而非固定串，栈里存的是「等待被闭合的左括号」
1544. 整理字符串 简单 消除条件变为「相邻两字符同字母异大小写」，判据从等值改成位运算
735. 小行星碰撞 中等 消除是带方向和大小的三种结局，栈顶可能连续弹多个，且当前元素也可能被销毁
1190. 反转每对括号间的子串 中等 栈里保存的不是字符而是待拼接的片段，出栈时做的是反转与合并而非丢弃
394. 字符串解码 中等 双栈分别保存倍数与前缀，出栈时要按倍数展开，是消除思路的构造版