leetcode 1910. Remove All Occurrences of a Substring [Python]

leetcode 1910. Remove All Occurrences of a Substring [Python]

题目做法有点儿扯，每次找到一个和part相同的子串就要删除，然后在新的string基础上继续比对。KMP值返回第一个找到重复part的位置。

class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        if part not in s:return s
        res = self.kmp(part, s)
        #print(res)
        s = list(s)
        #print(s)
        index = res
        for i in range(len(part)):
            s[index + i] = ' '
        newstr = ''
        for char in s:
            if char != ' ':
                newstr += char
        #print(newstr)
        return self.removeOccurrences(newstr, part)
        
    def kmp(self, p, s):
        m = len(p)
        p = ' ' + p
        n = len(s)
        s = ' ' + s
        ne = [0]*100010
        j =0
        res = -1
        for i in range(2, m+1):
            while j and p[i] != p[j+1]:
                j = ne[j]
            if p[i] == p[j+1]:
                j += 1
            ne[i] = j
        j = 0
        for i in range(1, n+1):
            while j and s[i] != p[j+1]:
                j = ne[j]
            if s[i] == p[j+1]:
                j += 1
            if j == m:
                return i-j
                j = ne[j]  
        return res