[LeetCode] 1910. Remove All Occurrences of a Substring

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

leetcode - Remove All Occurrences of a Substring

문제 유형: 스택, 문자열 처리

문제 난이도: 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.

 

두 문자열 s와 part가 주어집니다.

s의 부분문자열로 part가 있는 경우, 가장 왼쪽의 part를 제거하는 연산을 가능한 만큼 수행한 이후의 값을 구하시오.

 

풀이

스택에 순차적으로 문자열을 담으면서, 만약 part의 끝이 이번 글자이고 스택의 크기가 part의 길이 이상이라면, 스택에서 글자를 꺼내면서 그것들이 part의 역문자라면, 모두 pop한채로 두면 된다. 실패 시, 다시 스택을 돌려놓는다.

 

스택에 있는 문자들을 합쳐 문자열로 만들고, 뒤집어서 반환한다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    return 0;
}();

class Solution {
public:
    string removeOccurrences(string s, string part) {
        int m = part.size();
        stack<char> stk;
        reverse(part.begin(), part.end());

        for(char ch : s) {
            stk.push(ch);
            if(stk.size() >= m && ch == part[0]) {
                stack<char> temp;
                bool flag = true;
                for(int i = 0; i < m; ++i) {
                    if(part[i] != stk.top()) {
                        flag = false;
                        break;
                    }
                    temp.push(stk.top());
                    stk.pop();
                }

                if(!flag) {
                    while(!temp.empty()) {
                        stk.push(temp.top());
                        temp.pop();
                    }
                }
            }
        }

        string ans = "";
        while(!stk.empty()) {
            ans += stk.top();
            stk.pop();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

 

Go

func removeOccurrences(s string, part string) string {
    stk := make([]byte, 0)
    m := len(part)

    for _, ch := range s {
        stk = append(stk, byte(ch))
        if len(stk) >= m && stk[len(stk)-1] == part[m-1] {
            offset := len(stk) - m
            flag := true
            for i := 0; i < m; i++ {
                if stk[offset + i] != part[i] {
                    flag = false
                    break
                }
            }

            if flag {
                stk = stk[:offset]
            }
        }
    }

    return string(stk)
}