删除字符串中所有出现的子串 图解题解
这道题到底在问什么
- 输入
- s="daabcbaabcbc", part="abc"
- 输出
- "dab" （依次抠掉 abc）
- 输入
- s="aaaaa", part="aa"
- 输出
- "a" （每次删最左的 aa）
最优解：一步一步想明白
- 3一句话套路:逐字符压栈,每次只盯栈顶 m 个看是否等于 part,命中即弹。下面一字一字演示这条规则。
- 4把下面这个空栈当作「结果串」。我们从左到右一个个读 s 的字符,读一个就压进栈,边压边检查栈顶。
- 5读到第 0 个字符 "d"(流里高亮),先把它压进栈顶。
- 6栈里还不到 3 个字符,凑不出 part,跳过检查,继续读下一个。
- 7读到第 1 个字符 "a"(流里高亮),先把它压进栈顶。
- 8栈里还不到 3 个字符,凑不出 part,跳过检查,继续读下一个。
- 9读到第 2 个字符 "a"(流里高亮),先把它压进栈顶。
- 10看栈顶最后 3 个字符:"daa"。和 part = "abc" 不相等,什么都不做,继续读下一个。
- 11读到第 3 个字符 "b"(流里高亮),先把它压进栈顶。
- 12看栈顶最后 3 个字符:"aab"。和 part = "abc" 不相等,什么都不做,继续读下一个。
- 13读到第 4 个字符 "c"(流里高亮),先把它压进栈顶。
- 14看栈顶最后 3 个字符:"abc"。正好等于 part = "abc",命中,下一帧把它们弹掉。
- 15把栈顶这 3 个字符整段弹出,相当于在结果串里抠掉一个 part。现在暴露出新的栈顶 "a",它会接受下一个字符的检查,连锁消除就靠这一步。
- 16读到第 5 个字符 "b"(流里高亮),先把它压进栈顶。
- 17看栈顶最后 3 个字符:"dab"。和 part = "abc" 不相等,什么都不做,继续读下一个。
- 18读到第 6 个字符 "a"(流里高亮),先把它压进栈顶。
- 19看栈顶最后 3 个字符:"aba"。和 part = "abc" 不相等,什么都不做,继续读下一个。
- 20读到第 7 个字符 "b"(流里高亮),先把它压进栈顶。
- 21看栈顶最后 3 个字符:"bab"。和 part = "abc" 不相等,什么都不做,继续读下一个。
- 22读到第 8 个字符 "c"(流里高亮),先把它压进栈顶。
- 23看栈顶最后 3 个字符:"abc"。正好等于 part = "abc",命中,下一帧把它们弹掉。
- 24把栈顶这 3 个字符整段弹出,相当于在结果串里抠掉一个 part。现在暴露出新的栈顶 "b",它会接受下一个字符的检查,连锁消除就靠这一步。
- 25整串扫完,栈里剩下 "dab" 就是删光所有 part 后的结果。整个过程只扫一遍 s,两段 "abc" 在压栈途中分别被检测到并弹出,无需反复整串查找,这正是栈法的精髓。
⚠️ 容易写错的地方
✗ 错：用 s.replace 反复整串替换
✓ 对：用栈一遍扫,边压边查栈顶
反复 replace 每轮都重扫整串,最坏 O(n²/m),且要小心新拼出的 part;栈法天然处理连锁消除
✗ 错：弹出后忘了新栈顶可能又凑成 part
✓ 对：栈法不用特意处理,新栈顶下一轮自动被检查
连锁消除栈法顺带就做了:下一个字符压入后照常比对栈顶,暴露的旧字符会一起被算进去
✗ 错：栈不足 m 个就去取末尾 m 个
✓ 对：先判断栈高 ≥ m 再比对
栈里字符不够会取到不存在的位置或误判,必须先做长度检查
完整代码（Python / C++ / Java）
Python
class Solution:
def removeOccurrences(self, s: str, part: str) -> str:
st = []
m = len(part)
for ch in s:
st.append(ch)
if len(st) >= m and ''.join(st[-m:]) == part:
del st[-m:]
return ''.join(st)C++
#include <string>
using namespace std;
class Solution {
public:
string removeOccurrences(string s, string part) {
string st;
int m = part.size();
for (char c : s) {
st.push_back(c);
if ((int)st.size() >= m && st.substr(st.size() - m) == part) st.erase(st.size() - m);
}
return st;
}
};Java
import java.util.*;
class Solution {
public String removeOccurrences(String s, String part) {
StringBuilder st = new StringBuilder();
int m = part.length();
for (char c : s.toCharArray()) {
st.append(c);
if (st.length() >= m && st.substring(st.length() - m).equals(part)) st.delete(st.length() - m, st.length());
}
return st.toString();
}
}复杂度
时间
O(n·m)
n 个字符各入栈一次,每次比对栈顶 m 个字符
空间
O(n)
栈最多装下整个 s,长度 n
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 删除字符串中所有出现的子串 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
和直接用 while 循环里反复 s = s.replace(part, "") 比,栈法好在哪?+
反复 replace 每一轮都要从头扫整个字符串找 part,且替换会生成新串,最坏要扫很多轮,复杂度可能退化。栈法只扫一遍 s,每个字符进栈一次、比对一次栈顶,连锁消除也在同一遍里顺手完成,整体 O(n·m) 且常数小、思路统一。
如果 part 很长(接近 n),复杂度会怎样?+
每次比对栈顶要看 m 个字符,所以是 O(n·m);当 m 接近 n 时最坏到 O(n²)。可以用滚动哈希或 KMP 把每次比对降到 O(1) 摊还,但本题数据规模(n、m ≤ 1000)下朴素栈法已足够快,工程上更清晰。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 删除字符串中所有出现的子串 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。