栈和队列-删除字符串中的所有相邻重复项

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

题目

输入一个字符串，且定义一个操作，对字符串连续的两个字符，若其相等则去除这两个字符，对字符串进行任意次操作，直到无相同的两个相邻字符输出最后的字符串。
示例1：输入：‘abccbas’; 输出：‘s’
示例2：输入：‘acca’; 输出： ‘’

思路

本题需要删除相邻的重复字符，其实和有效的括号一样，有相等的就去除，可以用栈来表示剩余未匹配的字符，遍历字符串，每次遍历都和栈顶元素比较，若相等去除栈顶元素，若不等则入栈。

复杂度

时间复杂度:

$O(n)$

空间复杂度:

$O(n)$

Code

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []
        for si in s:
            if not len(stack):
                stack.append(si)
                continue
            top = stack[-1]
            if si == top:
                stack.pop()
            else:
                stack.append(si)
        
        return ''.join(stack)