[LeetCode] 1910. Remove All Occurrences of a Substring (Python)

Problem

 

Solution

string

part에 해당하는 문자가 s 에 존재하지 않을 때까지 제거하는 문제.

왜 replace를 생각하지 못했을까 ㅜㅜ

 

<다른 풀이>

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

• 시간복잡도 : O(N) , 최악의 경우 O(N^2)
• 공간복잡도: O(N)

Code

class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        idx = 0
        n = len(part)

        while(idx < len(s)):
            subStr = s[idx:idx+n]
            if (subStr == part):
                s = s[:idx] + s[idx+n:]
                #print(idx, s)
                idx = 0
            else:
                idx += 1

        return s

 

Complexity

Time Complexity

위와 마찬가지로 O(N), 최악의 경우 O(N^2)

 

Space Complexity

새로운 문자열이 반복 생성되므로 O(N)