检查替换后的词是否有效 图解题解

这道题到底在问什么

输入

s = "aabcbc"

输出

true（抹掉两段 abc 后变空）

输入

s = "abccba"

输出

false（抹到后面卡住,留有残余）

最优解：一步一步想明白

1. 3记牢这套「逐字压栈、栈顶凑齐 abc 就整段回收、最后看栈空不空」,下面每一帧都在套它。
2. 4上方一排是要从左到右处理的 6 个字符 a、a、b、c、b、c。下方竖着的格子就是栈,现在空空的。我们一个字符一个字符地往栈里压,盯紧栈顶,只要顶上凑出 a、b、c 三个,就把它们一起回收。
3. 5先做个便宜的剪枝:合法串每段 abc 贡献 3 个字符,所以总长一定是 3 的倍数。这里长度 6,6 除以 3 余 0,过关,值得继续扫。如果长度除以 3 不为 0,可以直接判 false,省得白扫。
4. 6处理 第 0 个 字符 a。它不是 c,不会触发回收,直接压进栈。现在栈里是 a,栈顶就一个字符,远没凑齐 abc,继续往后走。
5. 7处理 第 1 个 字符,又是 a,照样压栈。现在栈里是两个 a。栈顶三个里没有 b、c,凑不齐,接着扫。
6. 8处理 第 2 个 字符 b,压栈。现在栈是 a、a、b。栈顶是 b,只差一个 c 就能凑出 abc 了,但 b 自己不触发回收,得等下一个真的是 c 才行。
7. 9处理 第 3 个 字符,是 c。c 是唯一能凑齐 abc 的收口字符,所以一遇到 c 就要警觉:先把它压进去,再看栈顶三个能不能恰好拼成 a、b、c。
8. 10把 c 压进栈,现在栈是 a、a、b、c。看栈顶最上面三个,自底向上正好是 a、b、c,恰好是一段完整的 abc。凑齐了,下一帧就把这三个一起回收掉。
9. 11把栈顶的 a、b、c 三个一起弹掉,相当于抹掉了刚拼出的一段 abc。栈从 a、a、b、c 缩回成单个 a。你看,c 一来就触发了一次回收,这正是栈干的活。
10. 12处理 第 4 个 字符 b,压栈。现在栈是 a、b,栈顶又只差一个 c 就能收口。继续看下一个。
11. 13处理 第 5 个 字符,又是 c。老规矩,先压进去,再检查栈顶三个是不是 abc。
12. 14压入 c,栈变成 a、b、c。栈顶三个自底向上正好是 a、b、c,又凑齐一段 abc,马上回收。
13. 15弹掉栈顶的 a、b、c,这一段 abc 也抹掉了。栈现在彻底空了。全部 6 个字符都处理完,栈里一干二净。
14. 166 个字符全部扫完,栈是空的,说明 "aabcbc" 能被一层层 abc 完整抹空,它就是合法串,返回 true。和开头说的答案对上了。
15. 17再看一个会失败的例子 "abccba",体会无效是怎么暴露的。栈清空重来,还是逐字压栈、栈顶凑齐 abc 就回收。注意看后半段它在哪一步卡住。
16. 18第一个字符 a,压栈,栈是 a。
17. 19第二个字符 b,压栈,栈是 a、b,等一个 c 收口。
18. 20第三个字符 c,压栈,栈是 a、b、c。栈顶三个正好是一段 abc,凑齐了,下一帧回收。
19. 21弹掉 a、b、c,栈又空了。前半截 abc 抹得很干净,目前一切正常。关键看第四个字符。
20. 22第四个字符又是 c,压进去,栈里只有一个 c。问题来了:栈顶这个 c 下面既没有 b 也没有 a,凑不出 abc,回收触发不了,这个 c 只能孤零零留在栈里。无效的苗头出现了。
21. 23第五个字符 b,压栈,栈是 c、b。注意顺序乱了:正常一段是底 a、中 b、顶 c,这里底下却是个 c,永远拼不回 abc。
22. 24最后一个字符 a,压栈,栈是 c、b、a。栈顶三个自底向上是 c、b、a,顺序正好反了,不是 abc,回收不了。字符扫完了,栈里还堵着三个。
23. 256 个字符扫完,栈里还剩 c、b、a 三个抹不掉。栈不空,说明 "abccba" 没法被一段段 abc 拼出来,返回 false。一个孤立的 c 把后面全带乱了,这就是无效的根源。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 3:
            return False
        t = []
        for c in s:
            t.append(c)
            if ''.join(t[-3:]) == 'abc':
                t[-3:] = []
        return not t

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 3) {
            return false;
        }
        string t;
        for (char c : s) {
            t.push_back(c);
            if (t.size() >= 3 && t.substr(t.size() - 3, 3) == "abc") {
                t.erase(t.end() - 3, t.end());
            }
        }
        return t.empty();
    }
};

import java.util.*;
class Solution {
    public boolean isValid(String s) {
        if (s.length() % 3 > 0) {
            return false;
        }
        StringBuilder t = new StringBuilder();
        for (char c : s.toCharArray()) {
            t.append(c);
            if (t.length() >= 3 && "abc".equals(t.substring(t.length() - 3))) {
                t.delete(t.length() - 3, t.length());
            }
        }
        return t.length() == 0;
    }
}

复杂度

面试官可能追问