049 · Remove All Adjacent Duplicates In String

algorithm

Published

July 1, 2026

My First Thoughts

这道题看起来比上一题稍微复杂一点。

题目要求一直删除相邻且相同的字符。也就是说，删除一对字符以后，左右两边原本不相邻的字符会重新接在一起，可能又形成新的相邻重复。

这个感觉和之前做过的括号闭合问题有点像：都只关心“最近还没有被处理掉的那个元素”。

结构好像叫栈吧，也就是后进先出？

所以可以弄一个列表，比如叫：

list1 = []

让它保存当前还没有被删除的字符。

遍历 s 的时候，如果当前字符和 list1 最后一个字符相等，就说明它们形成了一对相邻重复字符，应该把 list1 最后一个字符移除，并且当前字符也不加入。

如果不相等，就把当前字符加入 list1。

最开始想到的代码大概是：

list1 = []

for char in s:
    if char == list1[-1]:
        list1.pop()
    else:
        list1.append(char)

return "".join(list1)

这个思路大概率就是正解。核心考点确实是：用列表维护当前结果，遇到能抵消的字符就删除列表末尾。

Why That Is Not Enough

上面的算法方向是对的，问题不在“用不用栈”，而是在一个 Python 的边界细节。

这句代码：

list1[-1]

表示取列表最后一个元素。

但如果 list1 还是空列表，就没有最后一个元素可以取。Python 不会给空列表返回一个特殊值，而是会直接报错。

比如一开始：

list1 = []

处理第一个字符时，如果直接判断：

char == list1[-1]

这里的 list1[-1] 就已经出错了。

所以在比较当前字符和栈顶字符之前，需要先确认列表里确实有元素：

if list1 and char == list1[-1]:

这里的 list1 本身可以当作布尔值使用：

空列表 [] 表示 False
非空列表表示 True

这样就能保证只有 list1 非空时，才会继续访问 list1[-1]。

Final Idea

保留原来的思路：用一个列表保存当前还有效的字符。

这个列表的末尾，就是当前结果里的最后一个字符。

每次读到一个新字符 char：

如果列表不空，并且 char 等于列表最后一个字符，说明它们相邻且相同，删除列表最后一个字符，当前字符也不加入
否则，把 char 加入列表

遍历结束后，列表里剩下的字符就是最终结果。因为答案要求字符串，所以最后用：

"".join(list1)

把列表拼回字符串。

Why It Works

从左到右处理字符串时，list1 始终表示“当前已经处理过的部分，在不断删除相邻重复字符以后剩下的结果”。

当新字符和 list1 最后一个字符不同，它们不会形成一对相邻重复字符，所以新字符应该保留下来：

list1.append(char)

当新字符和 list1 最后一个字符相同，它们正好形成一对需要删除的相邻重复字符。

列表最后一个字符已经在 list1 里，所以删除它：

list1.pop()

当前字符也不加入列表，相当于这一对字符一起消失。

删除以后，新的列表末尾会自动变成更早的字符。后面的字符继续进入循环时，就能自然处理“删除后重新相邻”的情况。

比如：

"abbaca"

处理到第二个 "b" 时，两个 "b" 抵消。后面处理到第二个 "a" 时，它又会和前面剩下的 "a" 抵消。这个过程不需要额外回头扫描，因为 list1 的末尾一直代表当前结果的最后一个有效字符。

Code

def removeDuplicates(s):
    list1 = []

    for char in s:
        if list1 and char == list1[-1]:
            list1.pop()
        else:
            list1.append(char)

    return "".join(list1)

Complexity

Time	\(O(n)\) - `n` 是 `s` 的长度；每个字符只处理一次
Space	\(O(n)\) - 最坏情况下没有相邻重复字符，列表会保存所有字符

Takeaway

当题目要求不断删除“最近形成的一对元素”时，可以用列表当栈。访问栈顶 list1[-1] 之前，要先确认列表不为空；空列表没有最后一个元素，不会返回默认值。

← Quiz