LeetCode 1003. 检查替换后的词是否有效
题目描述
题意分析
从空串开始，每次可以在任意位置插入一个连续的
abc，判断能否通过若干次这样的操作得到给定字符串。每次插入必须保持a、b、c的顺序。可以反向思考：合法构造的最后一次插入，对应最终字符串中的某个连续
abc。把它删除就回到上一个状态，因此问题等价于能否反复删除连续abc，最终变成空串。字符数量相同只是必要条件，排列结构也必须符合消除规则。
解法：栈模拟消除
核心思路
[!blue]
用栈保存已经扫描部分在消除后剩下的字符，始终保持栈内没有可直接删除的连续
abc。从左到右读取一个新字符后，先把它追加到栈顶，再判断末尾三个字符是否恰好是abc。新匹配只可能出现在栈顶。因为加入当前字符之前，旧栈已经没有
abc；如果新出现一个匹配，它必须使用刚加入的字符，而且以它结尾。命中后把三个字符一起弹出，就完成一次合法的逆向操作。删除这一段之后，只剩旧栈更短的一个前缀，旧栈原本没有可消除模式，所以不需要在同一轮再反复检查。后续字符到来时，会与当前残留前缀重新组成可能的匹配，自然处理插入之间的嵌套关系。
立即消除不会错过合法方案：两个当前存在的
abc不可能共用字符，删掉其中一个不会破坏另一个，删除顺序可以交换。因此可以优先删除扫描中已经完整出现的模式，而不用分支尝试不同删除位置。如果最终栈空，记录下来的删除操作倒过来就是从空串构造原串的过程，说明有效；若仍有字符，栈内又没有任何
abc可删，就无法继续还原为空，返回无效。不能只因为中途成功消除过一段就返回真。
解题步骤
- 创建空字符栈，从左到右扫描字符串。
- 每次将当前字符压入栈。
- 栈至少有三个字符且末尾依次为
a、b、c时，一次移除这三项。- 全部扫描结束后，只在栈为空时返回
true。
代码实现
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);
// 新出现的 abc 只可能位于栈顶，消除一次即可。
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)
// 新出现的 abc 只可能位于栈顶，消除一次即可。
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)$，最坏需要保存整个残留串。
关键点总结
[!green]
- 反向操作把构造问题变成消除问题。
- 栈中保存残留串，不是原字符串的连续区间。
- 判断是否有效必须看最终残留，而不是是否曾经消除成功。
易错点总结
[!yellow]
- 只比较三种字符数量：数量匹配不代表顺序与嵌套方式符合插入规则。
- 直接读取末尾三项而不检查长度：短前缀尚不足一组，会越界。
- 消除成功一次就返回真：还需要检查整个字符串，残留任何无法继续消除的字符都无效。
- 把栈当成原串连续区间：栈保存的是删除后的残留顺序，原本隔开的字符可能在消除后变为相邻。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1047. 删除字符串中的所有相邻重复项 | 简单 | 同样将局部可消除模式放在栈尾处理，本题模式固定为abc，原题删除相邻相同字符。 |
| 2390. 从字符串中移除星号 | 中等 | 同样用栈保存未消除前缀，本题由字符组合触发删除，原题由显式星号触发。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！