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

 

 

 

난이도: Medium

문제 설명

---

 

Given two strings s and part, perform the following operation on s until all occurrences of the substring part are removed:

• Find the leftmost occurrence of the substring part and remove it from s.

Return s after removing all occurrences of part.

A substring is a contiguous sequence of characters in a string.

 

문제 예제

---

Example 1:

Input: s = "daabcbaabcbc", part = "abc"
Output: "dab"
Explanation: The following operations are done:
- s = "daabcbaabcbc", remove "abc" starting at index 2, so s = "dabaabcbc".
- s = "dabaabcbc", remove "abc" starting at index 4, so s = "dababc".
- s = "dababc", remove "abc" starting at index 3, so s = "dab".
Now s has no occurrences of "abc".

Example 2:

Input: s = "axxxxyyyyb", part = "xy"
Output: "ab"
Explanation: The following operations are done:
- s = "axxxxyyyyb", remove "xy" starting at index 4 so s = "axxxyyyb".
- s = "axxxyyyb", remove "xy" starting at index 3 so s = "axxyyb".
- s = "axxyyb", remove "xy" starting at index 2 so s = "axyb".
- s = "axyb", remove "xy" starting at index 1 so s = "ab".
Now s has no occurrences of "xy".

 

제한 사항

---

• 1 <= s.length <= 1000
• 1 <= part.length <= 1000
• s​​​​​​ and part consists of lowercase English letters.

 

✏️ Solution(솔루션)

---

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

        return s

 

replace함수를 이용해서 쉽게 구현했다.

 

s에 part가 있을 때까지 s의 part를 ''로 replace했다.

 

이 때 맨 처음 나온 part를 지워야 하기 때문에 replace 마지막 인자로 1을 넣어주었다.

 

1을 넣지 않는다면 s에 있는 모든 part가 replace되기 때문에 문제 설명 만족하지 못하기 때문이다.

 

---

 

풀고 나서 너무 날먹으로 문제를 푼 것같아 문제가 원하는 방향인 stack으로도 다시 풀어봤다.

 

class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        stack = []
        n = len(s)
        m = len(part)
        
        for i in range(n):
            stack.append(s[i])
            if len(stack) >= m and ''.join(stack[-m:]) == part:
                for _ in range(m):
                    stack.pop()

        return ''.join(stack)

 

s의 요소를 모두 탐색하면서 stack에 넣어주었다.

이때 ''.join(stack[-m:])이 part와 같다면 part의 길이만큼 stack.pop()을 해주었다.

 

이렇게 하면 문제가 원하는대로 제일 먼저 나오는 part를 계속 뺐기 때문에 stack에 원하는 결과가 들어가있다

 

마지막에는 stack에 있는 요소들을 문자열로 바꾸어 반환하여 정답을 맞출 수 있었다.

---

문제: 1910. Remove All Occurrences of a Substring

 

깃허브: github

algorithmPractice/LeetCode/2021-remove-all-occurrences-of-a-substring at main · laewonJeong/algorithmPractice