1047. Remove All Adjacent Duplicates In String

문제

You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.

We repeatedly make duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.

https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/

접근

#스택

간단한 스택 구조로 인접한 중복을 모두 제거할 수 있다. 재귀법으로도 해결이 가능하지만, 시간초과가 발생한다.

코드

class Solution:
    def removeDuplicates(self, s: str) -> str:
        ans=[] # stack
        for a in s:
            if len(ans)>0 and ans[-1]==a:
                ans.pop()
            else:
                ans.append(a)
        return("".join(ans))

효율성

Runtime: 214 ms, faster than 38.96% of Python3 online submissions for Remove All Adjacent Duplicates In String.
Memory Usage: 14.9 MB, less than 52.58% of Python3 online submissions for Remove All Adjacent Duplicates In String.