LeetCode 题解工作台
删除一个字符串中所有出现的给定子字符串
给你两个字符串 s 和 part ，请你对 s 反复执行以下操作直到 所有 子字符串 part 都被删除： 找到 s 中 最左边 的子字符串 part ，并将它从 s 中删除。 请你返回从 s 中删除所有 part 子字符串以后得到的剩余字符串。 一个 子字符串 是一个字符串中连续的字符序列。 示例…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 栈·状态
答案摘要
我们循环判断 中是否存在字符串 ，是则进行一次替换，继续循环此操作，直至 中不存在字符串 ，返回此时的 作为答案字符串。 时间复杂度 $O(n^2 + n \times m)$，空间复杂度 $O(n + m)$。其中 和 分别是字符串 和字符串 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
给你两个字符串 s 和 part ，请你对 s 反复执行以下操作直到 所有 子字符串 part 都被删除：
- 找到
s中 最左边 的子字符串part，并将它从s中删除。
请你返回从 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.length <= 10001 <= part.length <= 1000s 和part只包小写英文字母。
解题思路
方法一：暴力替换
我们循环判断 中是否存在字符串 ，是则进行一次替换，继续循环此操作，直至 中不存在字符串 ，返回此时的 作为答案字符串。
时间复杂度 ，空间复杂度 。其中 和 分别是字符串 和字符串 的长度。
class Solution:
def removeOccurrences(self, s: str, part: str) -> str:
while part in s:
s = s.replace(part, '', 1)
return s
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n + m) |
| 空间 | O(n + m) |
面试官常问的追问
外企场景- question_mark
Look for candidates who use stack-based state management efficiently.
- question_mark
Evaluate if the candidate handles the repeated removal of part effectively.
- question_mark
Assess whether the candidate understands the complexities involved in removing part and handling potential new occurrences.
常见陷阱
外企场景- error
Forgetting to check for new occurrences of part after each removal, leading to incorrect results.
- error
Using inefficient string operations like string slicing or replacing, which could increase time complexity.
- error
Overcomplicating the solution by failing to leverage the stack for optimal string state management.
进阶变体
外企场景- arrow_right_alt
What if part appears multiple times in a row? The candidate should ensure the solution can handle repeated consecutive occurrences of part efficiently.
- arrow_right_alt
What if part is not present in s at all? Ensure that the candidate can handle the case where no removals are needed.
- arrow_right_alt
What if part is equal to the entire string s? This should result in an empty string after the removal.