5.4 删除字符串中的所有相邻重复项（LC1047-E）

算法：

相对于20. 有效的括号 (opens new window)来说其实也是匹配问题，20. 有效的括号 是匹配左右括号，本题是匹配相邻元素，最后都是做消除的操作。

本题也是用栈来解决的经典题目。

那么栈里应该放的是什么元素呢？

我们在删除相邻重复项的时候，其实就是要知道当前遍历的这个元素，我们在前一位是不是遍历过一样数值的元素，那么如何记录前面遍历过的元素呢？

比如“abbaca”

所以就是用栈来存放，那么栈的目的，就是存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素。如果栈里有相同的元素，就pop该元素。

从栈中弹出剩余元素，此时是字符串ac，因为从栈里弹出的元素是倒序的，所以再对字符串进行反转一下，就得到了最终的结果。

实际操作：

可以直接用字符串模拟栈，这样就不用再转换了。不过python中字符串不可变，所以可以用列表模拟栈，最后再转成字符串。这样也就不需要反转了。

python可以使用列表（List）来实现栈的功能（没有直接的表示栈的代码）。列表的 **`

append()

** 方法可以用于将元素入栈，**

pop()

`** 方法可以用于将元素出栈。这样，我们可以使用列表的末尾作为栈的顶部。

调试过程：

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []
        for item in s:
            #若栈顶等于item，则要消除
            #栈顶用stack[-1]表示，写得时候就要想到，前提是stack非空
            if stack and stack[-1] == item:
                stack.pop()
            else:
                stack.append(item)
            #最后要返回一个字符串，可以用join函数
            return "".join(stack)

原因：**`

return

** 语句的位置不正确。它应该放在 **

for

`** 循环的外部，以便在遍历完整个字符串后返回最终的结果。

正确代码：

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []
        for item in s:
            #若栈顶等于item，则要消除
            #栈顶用stack[-1]表示，写得时候就要想到，前提是stack非空
            if stack and stack[-1] == item:
                stack.pop()
            else:
                stack.append(item)
            #最后要返回一个字符串，可以用join函数
        return "".join(stack)

时间空间复杂度：

• 时间复杂度：O(n)，其中 n 是输入字符串的长度。代码通过一次遍历字符串（for循环），对每个字符进行入栈和出栈操作，所以时间复杂度是线性的。
• 空间复杂度：O(n)，其中 n是输入字符串的长度。在最坏情况下，当输入字符串中的字符都不相同时，栈的大小将达到输入字符串的长度。因此，空间复杂度与输入字符串的长度成正比。

对于 return "".join(stack) 这行代码，复杂度的计算方式如下：

时间复杂度：O(n)，其中 n 是最终生成的字符串的长度。join() 函数需要遍历栈中的字符并将它们逐个拼接起来，所以时间复杂度与最终生成的字符串的长度成正比。

空间复杂度：O(n)，其中n是最终生成的字符串的长度。在拼接字符串时，join() 函数会创建一个新的字符串对象，并将栈中的字符逐个复制到新的字符串中。因此，空间复杂度与最终生成的字符串的长度成正比。

需要注意的是，join() 函数的空间复杂度只考虑了最终生成的字符串所占用的额外空间，而不包括栈 stack 的空间。栈 stack 的空间复杂度已经在之前的回答中进行了说明，它是 O(n)，其中 n是输入字符串的长度。 因此，总的空间复杂度可以看作是 O(n)，其中 n是最终生成的字符串的长度。