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

标签: 字符串

难度: Medium

给你两个字符串 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 <= 1000
  • 1 <= part.length <= 1000
  • s​​​​​​ 和 part 只包小写英文字母。

Submission

运行时间: 22 ms

内存: 16.0 MB

class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        while part in s:
            s = s.replace(part, '', 1)  # Replace the first occurrence of 'part' with an empty string
        return s

solution = Solution()
print(solution.removeOccurrences("daabcbaabcbc", "abc"))  # Output: "dab"
print(solution.removeOccurrences("axxxxyyyyb", "xy"))     # Output: "ab"

Explain

这个题解采用了一个直观的方法来处理问题。它使用了Python的字符串方法 `replace` 来删除字符串 `s` 中的第一个出现的子字符串 `part`。这个过程是在一个循环中实现的，循环的条件是只要 `part` 还存在于 `s` 中就继续执行。通过不断替换第一次出现的 `part` 直到 `s` 中没有 `part`，最终返回修改后的字符串 `s`。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        # 循环直到 'part' 不再是 's' 的子字符串
        while part in s:
            # 用空字符串替换 's' 中第一次出现的 'part'
            s = s.replace(part, '', 1)
        # 返回处理后的字符串
        return s

solution = Solution()
print(solution.removeOccurrences("daabcbaabcbc", "abc"))  # Output: "dab"
print(solution.removeOccurrences("axxxxyyyyb", "xy"))     # Output: "ab"

Explore

使用 `replace` 方法的主要原因是其简洁性和效率。Python中的 `replace` 方法是用C语言编写的，因此在执行字符串替换操作时比手动实现的代码（通常使用Python的循环和字符串拼接）速度更快，更优化。此外，使用现有的库函数可以减少代码的复杂性和出错的可能性，使代码更易于理解和维护。

在每次循环迭代中检查 `part` 是否存在于 `s` 会导致每次都需遍历整个字符串 `s` 来查找 `part`，这在 `s` 长度很长时会显著影响性能。尤其是当 `part` 非常短且频繁出现时，这种方法可能会导致多次不必要的字符串扫描，从而增加了整体的时间复杂度。

是的，`replace` 方法会在每次调用时遍历整个字符串 `s` 来查找所有出现的 `part`。这意味着即使 `part` 在 `s` 的前部就被找到并替换了，`replace` 方法仍会继续检查后面的部分。这种全字符串扫描的方法在 `part` 频繁出现或 `s` 非常长时，会导致效率低下，特别是在循环中多次使用 `replace` 方法的情况下，每次循环都可能导致重复的全字符串扫描。

当 `part` 频繁出现时，可以考虑使用更高效的字符串处理算法，例如 KMP 算法、Rabin-Karp 算法或者 Boyer-Moore 算法。这些算法优化了字符串搜索过程，减少了不必要的比较和回溯。另一种方法是使用栈或其他数据结构，边遍历 `s` 边处理，当遇到匹配 `part` 的情况时进行特定操作，这样可以避免多次全字符串扫描，提高效率。