class Solution {
public:
string removeOccurrences(string s, string part) {
}
};
1910. 删除一个字符串中所有出现的给定子字符串
给你两个字符串 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 只包小写英文字母。原站题解
python3 解法, 执行用时: 32 ms, 内存消耗: 15 MB, 提交时间: 2022-11-27 12:14:23
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
python3 解法, 执行用时: 48 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-27 12:13:52
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)
golang 解法, 执行用时: 4 ms, 内存消耗: 2.2 MB, 提交时间: 2022-11-27 12:13:05
func removeOccurrences(s string, part string) string {
if len(s)==0{return s}
stack:=[]byte{}
sn,pn:=len(s),len(part)
for i:=0;i<sn;i++{
stack = append(stack,s[i])
if s[i]==part[pn-1]{
if len(stack)>=pn{
st:= string(stack[len(stack)-pn:])
if st==part{
stack=stack[:len(stack)-pn]
}
}
}
}
return string(stack)
}
python3 解法, 执行用时: 44 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-27 12:12:43
class Solution:
def removeOccurrences(self, s: str, part: str) -> str:
while part in s:
t=s.index(part)
s=s[:t]+s[t+len(part):]
return s
python3 解法, 执行用时: 44 ms, 内存消耗: 15.2 MB, 提交时间: 2022-11-27 12:12:21
class Solution:
def removeOccurrences(self, s: str, part: str) -> str:
m = len(part)
pi1 = [0] * m # part 的前缀数组
# 更新 part 的前缀数组
j = 0
for i in range(1, m):
while j > 0 and part[i] != part[j]:
j = pi1[j-1]
if part[i] == part[j]:
j += 1
pi1[i] = j
res = []
pi2 = [0] # res 的前缀数组
for ch in s:
# 模拟从左至右匹配的过程
res.append(ch)
# 更新 res 的前缀数组
j = pi2[-1]
while j > 0 and ch != part[j]:
j = pi1[j-1]
if ch == part[j]:
j += 1
pi2.append(j)
if j == m:
# 如果匹配成功，那么删去对应后缀
pi2[-m:] = []
res[-m:] = []
return "".join(res)
python3 解法, 执行用时: 48 ms, 内存消耗: 15 MB, 提交时间: 2022-11-27 12:12:00
class Solution:
def removeOccurrences(self, s: str, part: str) -> str:
m = len(part)
res = ""
for ch in s:
# 模拟从左至右匹配的过程
res += ch
if len(res) >= m and res[-m:] == part:
# 如果匹配成功，那么删去对应后缀
res = res[:-m]
return res