5781.删除一个字符串中所有出现的给定子字符串

https://leetcode-cn.com/problems/remove-all-occurrences-of-a-substring/solution/5781shan-chu-yi-ge-zi-fu-chuan-zhong-suo-agj2/

难度：中等

题目

给你两个字符串 s 和 part ，请你对 s 反复执行以下操作直到 所有 子字符串 part 都被删除：

找到 s 中 最左边 的子字符串 part ，并将它从 s 中删除。 请你返回从 s 中删除所有 part 子字符串以后得到的剩余字符串。

一个 子字符串 是一个字符串中连续的字符序列。

提示：

• 1 <= s.length <= 1000
• 1 <= part.length <= 1000
• s 和 part 只包小写英文字母。

示例

示例 1：

输入：s = "daabcbaabcbc", part = "abc"
输出："dab"
解释：以下操作按顺序执行：
- s = "daabcbaabcbc" ，删除下标从 2 开始的 "abc" ，得到 s = "dabaabcbc" 。
- s = "dabaabcbc" ，删除下标从 4 开始的 "abc" ，得到 s = "dababc" 。
- s = "dababc" ，删除下标从 3 开始的 "abc" ，得到 s = "dab" 。
此时 s 中不再含有子字符串 "abc" 。
示例 2：

输入：s = "axxxxyyyyb", part = "xy"
输出："ab"
解释：以下操作按顺序执行：
- s = "axxxxyyyyb" ，删除下标从 4 开始的 "xy" ，得到 s = "axxxyyyb" 。
- s = "axxxyyyb" ，删除下标从 3 开始的 "xy" ，得到 s = "axxyyb" 。
- s = "axxyyb" ，删除下标从 2 开始的 "xy" ，得到 s = "axyb" 。
- s = "axyb" ，删除下标从 1 开始的 "xy" ，得到 s = "ab" 。
此时 s 中不再含有子字符串 "xy" 。

分析

作为中等题，这道不是很难，做过类似的括号匹配等同类型题目，立刻就能想到通过栈来处理。

• 栈操作

1. 循环s进行入栈操作
2. 当栈内元素>= len(part) 并且相等时，将数据弹出
3. 最终将栈内数据''.join(stack)返回

• 字符串模拟
  由于这道题两个入参都是字符串，所以我们通过字符串来模拟栈操作

• 无赖的省事儿解法
  这里分享一个虽然很无赖的解法，但真的很欢乐，我们通过无线replace替换来完成这道题。
  这么写真的好赖皮，就是不知道面试的时候，会不会被打，哈哈。

解题

栈解题

class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        stack, part, ln = [], list(part), len(part)
        for i in s:
            stack.append(i)
            if len(stack) >= len(part):
                while stack[len(stack) - len(part):] == part:
                    for _ in range(len(part)):
                        stack.pop()
        return ''.join(stack)

字符串模拟

class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        ret = ''
        ln = len(part)
        for i in s:
            ret += i
            while ret.endswith(part):
                ret = ret[:len(ret) - ln]
        return ret

replace替换

class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        while part in s:
            s = s.replace(part,'')
        return s

字符串模拟

欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。

我的个人博客：https://qingfengpython.cn

力扣解题合集：https://github.com/BreezePython/AlgorithmMarkdown