Question

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

English Version

题目描述

给你两个字符串 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 只包小写英文字母。

解法

方法一：暴力替换

我们循环判断 $s$ 中是否存在字符串 $part$，是则进行一次替换，继续循环此操作，直至 $s$ 中不存在字符串 $part$，返回此时的 $s$ 作为答案字符串。

时间复杂度 $O(n^2 + n \times m)$，空间复杂度 $O(n + m)$。其中 $n$ 和 $m$ 分别是字符串 $s$ 和字符串 $part$ 的长度。

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

class Solution {
  public String removeOccurrences(String s, String part) {
    while (s.contains(part)) {
      s = s.replaceFirst(part, "");
    }
    return s;
  }
}

class Solution {
public:
  string removeOccurrences(string s, string part) {
    int m = part.size();
    while (s.find(part) != -1) {
      s = s.erase(s.find(part), m);
    }
    return s;
  }
};

func removeOccurrences(s string, part string) string {
  for strings.Contains(s, part) {
    s = strings.Replace(s, part, "", 1)
  }
  return s
}

function removeOccurrences(s: string, part: string): string {
  while (s.includes(part)) {
    s = s.replace(part, '');
  }
  return s;
}