华为 OD 训练营 · 题解精讲
LC1047. 删除字符串中的所有相邻重复项
LC1047. 删除字符串中的所有相邻重复项 如果作业完成有难度，可以查看我的讲解视频。
题目描述
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。 在 S 上反复执行重复项删除操作，直到无法继续删除。 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。 示例： 输入："abbaca" 输出："ca" 解释： 例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。 提示： 1 <= S.length <= 20000 S 仅由小写英文字母组成。
题目解析
解题思路
本题的核心是模拟“相邻重复项删除”的过程。由于删除一对相邻相同字符后，可能使原本不相邻的字符变成相邻并再次触发删除，因此需要一种能够“回溯”并比较当前字符与上一个未删除字符的数据结构——栈。
算法使用一个栈来存储尚未被删除的字符。遍历字符串中的每个字符 cur：
- 如果栈为空，直接将
cur入栈。 - 如果栈非空且栈顶字符不等于
cur，说明当前字符不会与栈顶形成重复，入栈。 - 如果栈非空且栈顶字符等于
cur，说明当前字符与栈顶字符是一对相邻重复项，需要删除它们。此时栈顶字符出栈（相当于删除），当前字符也不入栈。
遍历结束后，栈中剩余字符按顺序拼接即为最终结果。
关键步骤
以输入 "abbaca" 为例，模拟栈的变化：
遍历字符 a : 栈 [] -> 入栈 -> [a]
遍历字符 b : 栈顶 a ≠ b，入栈 -> [a, b]
遍历字符 b : 栈顶 b = b，出栈 -> [a]
遍历字符 a : 栈顶 a = a，出栈 -> []
遍历字符 c : 栈 []，入栈 -> [c]
遍历字符 a : 栈顶 c ≠ a，入栈 -> [c, a]
最终结果: "ca"复杂度分析
- 时间复杂度：O(N)，其中 N 为字符串长度。每个字符最多入栈一次、出栈一次。
- 空间复杂度：O(N)，最坏情况下（如字符串无任何相邻重复），栈中存储所有字符。
参考代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/submissions/
class Solution:
def removeDuplicates(self, s: str) -> str:
# 1、两个相邻且相同字符会被同时删除
# 2、删除字符串中两个相邻并且相同的字符后可能会产生一组新的相邻并且相同的字符，需要继续删除
# 说明需要记录之前的元素，将最靠近现在访问的元素与现在正在访问的元素进行对比
# 使用栈
stack = []
# 从头到尾访问所有的元素
# 正在访问的元素
for cur in s:
# 在访问过程中
# 1、如果栈为空，直接把当前访问的元素添加进去
if not stack :
# 直接把当前访问的元素添加进去
stack.append(cur)
# 2、如果栈不为空，并且栈顶元素不等于正在访问的元素
elif cur != stack[-1] :
# 也把当前访问的元素添加进去
stack.append(cur)
# 3、如果栈不为空，并且栈顶元素等于正在访问的元素
else:
# 说明这两个元素应该被删除，那么不仅当前这个元素无法加入到栈，同时和这个元素相同的栈顶元素得从栈中移除
stack.pop()
# 返回结果
return "".join(stack)
四、复杂度分析
时间复杂度：O(N)，因为对输入字符串 S 遍历了一次。
空间复杂度：O(N)，最坏情况下，栈的大小会与输入字符串 S 的大小相等。