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

约 4 分钟
文章信息 12 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 20-50 字节跳动 微软 美团 阿里巴巴 快手 腾讯 京东
标签
字符串 栈 元素去重问题
目录

题目描述

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

image-20250419074249297

题意分析

规则很简单：只要串里存在两个相邻且相同的字符，就把这一对整体删掉；反复执行直到再也找不到这样的一对为止，返回最终剩下的字符串。题目额外保证答案唯一，也就是说删除的先后顺序不影响最终结果，这一句是允许我们只按一个固定顺序处理的依据。
真正需要警惕的是删除的连锁效应：删掉中间一对之后，原本被它隔开的左右两个字符会贴到一起，可能立刻构成新的一对。所以这不是「扫一遍把所有相邻重复对删掉」就能收工的任务，删除必须能往回传播。
约束信号是长度上限十万、全为小写字母。十万意味着每删一对就从头重扫的 $O(n^2)$ 做法有超时风险，必须让每个字符只被处理常数次。
边界：像 "abba" 这样能被彻底消完的输入要返回空字符串而不是 null；没有任何相邻重复的输入要原样返回；长度为 1 的串永远原样返回。

解法：栈模拟相邻抵消

核心思路

删除一对字符后，它左右两侧的字符会重新相邻，因此只检查原字符串中的相邻对会漏掉连锁删除。例如 "abbaca" 删除 bb 后，两个 a 才会相邻并继续被删除。

从左到右处理时，不需要反复扫描整串。维护一个栈，使它始终保存“当前已读前缀彻底删除相邻重复项后的结果”。读入字符 ch 时，它只可能与栈顶相邻：

  • 栈顶等于 ch：弹出栈顶，当前字符也被这一对消耗；
  • 否则：将 ch 压栈。

这是循环不变量：处理完前 i 个字符后，栈内正好是该前缀的最终结果，并且内部不存在相邻重复字符。加入第 i + 1 个字符时，历史部分已经稳定，新冲突只能发生在末尾，因此一次比较就能恢复不变量。归纳到整串，栈内就是答案。

解题步骤

  1. 创建空字符栈。Java 可直接用 StringBuilder 的末尾充当栈顶，Go 使用 []byte。
  2. 从左到右读取每个字符。
  3. 若栈非空且栈顶与当前字符相同，弹出栈顶。
  4. 否则将当前字符压栈。
  5. 扫描结束后按原顺序返回栈中字符，不需要反转。

以 "abbaca" 为例，栈依次变化为 "" -> "a" -> "ab" -> "a" -> "" -> "c" -> "ca"：第二个 b 消掉栈顶 b，随后读到的 a 又消掉此前留下的 a，连锁效果自然完成，最终得到 "ca"。

代码实现

class Solution {
    public String removeDuplicates(String s) {
        StringBuilder stack = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            int top = stack.length() - 1;
            if (top >= 0 && stack.charAt(top) == ch) {
                stack.deleteCharAt(top);
            } else {
                stack.append(ch);
            }
        }
        return stack.toString();
    }
}

func removeDuplicates(s string) string {
    stack := make([]byte, 0, len(s))
    for i := 0; i < len(s); i++ {
        if len(stack) > 0 && stack[len(stack)-1] == s[i] {
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, s[i])
        }
    }
    return string(stack)
}

复杂度分析

  • 时间复杂度：O(n)。每个字符只会入栈一次、出栈至多一次。
  • 空间复杂度：O(n)。没有字符被删除时，栈需要保存整个字符串。

关键点总结

  • 删除会改变相邻关系；栈用回退栈顶的方式承接这种连锁影响。
  • 状态应定义为“已读前缀化简后的最终结果”，而不是原串中尚未处理的位置。
  • 当前字符只与栈顶比较，因为栈顶是化简后与它真正相邻的字符。
  • 面试追问“删除连续 k 个重复字符”时，可把栈元素扩展为“字符 + 连续次数”，计数达到 k 时弹出。

易错点总结

  • 只按原字符串下标跳过相邻重复对，会漏掉删除后新形成的重复。例如 "abbaca" 会漏删 aa。
  • 比较栈顶前必须先判断栈是否为空，否则全部抵消后再次读取会越界。
  • 匹配时只弹出已有的栈顶，当前字符不入栈；若再把当前字符压回去，就没有真正删除一对。
  • 栈保存的是答案的正向顺序，遍历结束后不能按出栈顺序直接拼接，否则结果会反转。
  • 使用不可变字符串反复拼接、截断会产生大量复制，最坏退化为 O(n^2)。

相似题目

题目 难度 考察点
1003. 检查替换后的词是否有效 中等 消除的是固定模式 abc 而非任意重复对，返回真假而不是剩余串
1209. 删除字符串中的所有相邻重复项 II 中等 满 k 个才消除，栈元素要扩成「字符 + 计数」的二元组