【代码随想录day11】删除字符串中的所有相邻重复项

题目 

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

思路

1.  如果当前栈为空或者当前元素和栈顶元素不相同，则直接把当前元素丢到栈中存储
2. 否则弹出栈顶元素，因为这里题目要求是两两配对，所以只需要弹出一次即可。假设题目要求所有连续相同字符都应该被删除，那就需要在else逻辑里用while把所有相同元素都删掉。

总体线性扫一遍，答案就会被存储在列表stack中，线性时间复杂度o(n)，空间复杂度o(n)。 

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []
        i = 0
        while i<len(s):
            if len(stack)==0 or stack[-1]!=s[i]:
                stack.append(s[i])
            else:
                stack.pop()
            i += 1
        return ''.join(stack)