今日题目

https://leetcode.com/problems/remove-all-occurrences-of-a-substring/description/

思路

本题需要删除字符串 “s” 中所有出现的子串 “part”。因此，我们可以不断检查 “s” 是否包含 “part”，若包含则将其删除，重复此操作直至不再出现为止。

方法

方法一： 使用栈来实现。遍历字符串，将字符依次压入栈中。当检测到栈顶的若干字符与 “part” 完全匹配时，将这些字符从栈中弹出。

方法二： 直接利用 Python 内置函数在原字符串 s 中查找并删除 “part”。

复杂度

  • 时间复杂度：$O(N\times M)$，N 为 s 的长度，M 为 part 的长度。

  • 空间复杂度：$O(1)$

代码

class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        st = []
        N = len(part)
        for ch in s:
            st.append(ch)
            if len(st) >= N:
                flag = True
                for i in range(1, N + 1):
                    if st[-i] != part[-i]:
                        print(st[-i], part[-i])
                        flag = False
                        break
                
                if flag:
                    for i in range(N):
                        st.pop()
    
        return ''.join(st)

Real Python

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