1047. 删除字符串中的所有相邻重复项 #

标签：字符串、栈
难度：简单

题目大意 #

给定一个全部由小写字母组成的字符串 S，重复的删除相邻且相同的字母，直到相邻字母不再有相同的。

比如 “abbaca”。先删除相邻且相同的字母 “bb”，变为 “aaca”，再删除相邻且相同的字母 “aa”，变为 “ca”，无相邻且相同的字母，即 “ca” 为最终结果。

解题思路 #

跟括号匹配有点类似。我们可以利用「栈」来做这道题。遍历字符串，如果当前字符与栈顶字符相同，则将栈顶所有相同字符删除，否则就将当前字符入栈。

代码 #

1
2
3
4
5
6
7
8
9


class Solution:
    def removeDuplicates(self, S: str) -> str:
        stack = []
        for ch in S:
            if stack and stack[-1] == ch:
                stack.pop()
            else:
                stack.append(ch)
        return "".join(stack)