删除字符串中所有出现的子串

一句话套路:逐字符压栈,每次只盯栈顶 m 个看是否等于 part,命中即弹。下面一字一字演示这条规则。

把下面这个空栈当作「结果串」。我们从左到右一个个读 s 的字符,读一个就压进栈,边压边检查栈顶。

读到第 0 个字符 "d"(流里高亮),先把它压进栈顶。

栈里还不到 3 个字符,凑不出 part,跳过检查,继续读下一个。

读到第 1 个字符 "a"(流里高亮),先把它压进栈顶。

栈里还不到 3 个字符,凑不出 part,跳过检查,继续读下一个。

读到第 2 个字符 "a"(流里高亮),先把它压进栈顶。

看栈顶最后 3 个字符:"daa"。和 part = "abc" 不相等,什么都不做,继续读下一个。

读到第 3 个字符 "b"(流里高亮),先把它压进栈顶。

看栈顶最后 3 个字符:"aab"。和 part = "abc" 不相等,什么都不做,继续读下一个。

读到第 4 个字符 "c"(流里高亮),先把它压进栈顶。

看栈顶最后 3 个字符:"abc"。正好等于 part = "abc",命中,下一帧把它们弹掉。

把栈顶这 3 个字符整段弹出,相当于在结果串里抠掉一个 part。现在暴露出新的栈顶 "a",它会接受下一个字符的检查,连锁消除就靠这一步。

读到第 5 个字符 "b"(流里高亮),先把它压进栈顶。

看栈顶最后 3 个字符:"dab"。和 part = "abc" 不相等,什么都不做,继续读下一个。

读到第 6 个字符 "a"(流里高亮),先把它压进栈顶。

看栈顶最后 3 个字符:"aba"。和 part = "abc" 不相等,什么都不做,继续读下一个。

读到第 7 个字符 "b"(流里高亮),先把它压进栈顶。

看栈顶最后 3 个字符:"bab"。和 part = "abc" 不相等,什么都不做,继续读下一个。

读到第 8 个字符 "c"(流里高亮),先把它压进栈顶。

看栈顶最后 3 个字符:"abc"。正好等于 part = "abc",命中,下一帧把它们弹掉。

把栈顶这 3 个字符整段弹出,相当于在结果串里抠掉一个 part。现在暴露出新的栈顶 "b",它会接受下一个字符的检查,连锁消除就靠这一步。

整串扫完,栈里剩下 "dab" 就是删光所有 part 后的结果。整个过程只扫一遍 s,两段 "abc" 在压栈途中分别被检测到并弹出,无需反复整串查找,这正是栈法的精髓。

边界:整串等于 part 删成空;part 不出现原样返回;重叠场景靠栈天然处理连锁。

两个高频追问:栈法对比反复 replace 的优势,以及 part 很长时的复杂度与优化方向。