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

题目描述

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。 在 S 上反复执行重复项删除操作，直到无法继续删除。 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。 示例： 输入："abbaca" 输出："ca" 解释： 例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。 提示： 1 <= S.length <= 20000 S 仅由小写英文字母组成。

题目解析

好的，没问题。作为一名 AlgoMooc 的算法老师，我的任务就是把这道题讲得明明白白，让你听完就能自己写出来。

我们开始吧。

---

题目在说什么

简单来说，就是给你一个字符串，里面有很多字母。你要像玩“消消乐”一样，把挨在一起的、一模一样的两个字母给删掉。

删掉之后，原本不相邻的字母可能会变成邻居。如果它们俩也相同，那就继续删。一直删，直到再也找不到两个相邻且相同的字母为止。

举个例子： 输入是 "abbaca"。 1. 先看 "ab**bb**aca"，中间有两个 b 挨着，把它们删掉，变成了 "a**a**ca"。 2. 再看 "a**aa**ca"，现在有两个 a 挨着了，再删掉，变成了 "ca"。 3. "ca" 里，c 和 a 不一样，没法再删了。所以最终答案就是 "ca"。

思路是怎么来的

这道题的关键在于，你删掉一对字母后，后面的字母会“往前靠”，可能会和前面的字母形成新的“重复对”。这就像我们玩一个“叠叠乐”或者“整理文件”的游戏。

生活化比喻：整理一摞盘子

想象一下，你面前有一摞盘子，每个盘子上都写了一个字母。你的任务是从上到下，把相邻的两个相同字母的盘子一起扔掉。

1. 你拿起第一个盘子，上面写着 a。因为你手里还没有任何盘子，所以先把它放在旁边，当作一个“待处理堆”的底部。 2. 你拿起第二个盘子，上面写着 b。你看看“待处理堆”最上面的盘子是什么？是 a。a 和 b 不一样，所以不能扔。你把 b 盘子也放到“待处理堆”上。现在堆里是 [a, b]（b 在最上面）。 3. 你拿起第三个盘子，上面写着 b。你再看“待处理堆”最上面的盘子，是 b。一模一样！ 这就意味着，你手里的这个 b 盘子和堆顶的那个 b 盘子是“相邻且相同”的。于是，你把堆顶的那个 b 盘子拿出来，和你手里的这个 b 盘子一起扔掉。现在“待处理堆”里只剩 [a]。 4. 你拿起第四个盘子，上面写着 a。你看堆顶，是 a。又一样！ 所以，你把堆顶的 a 拿出来，和手里的 a 一起扔掉。现在“待处理堆”空了。 5. 你拿起第五个盘子，上面写着 c。堆是空的，所以把 c 放上去。堆里是 [c]。 6. 你拿起第六个盘子，上面写着 a。堆顶是 c，不一样。把 a 放上去。堆里是 [c, a]。 7. 所有盘子都检查完了。现在“待处理堆”里剩下的盘子，从上到下是 a 和 c。把它们倒过来（因为我们是先拿最上面的），就是最终结果 "ca"。

你看，这个“待处理堆”完美地模拟了删除过程。它最重要的作用就是：永远让你知道“当前字符”的“前一个邻居”是谁。 这个“前一个邻居”就是堆顶的那个字符。这个“堆”在编程里就叫 栈 (Stack)。

代码逐步拆解

现在，我们来看参考代码，看看它是怎么实现这个“叠盘子”过程的。

class Solution {
    public String removeDuplicates(String S) {
        // 1. 创建一个栈，用来放“待处理的盘子”
        Stack<Character> stack = new Stack<>();

        // 2. 开始遍历字符串 S 中的每一个字符（就像依次拿起每个盘子）
        for (int i = 0; i < S.length(); i++) {

            // 当前拿到的字符（盘子）
            Character cur = S.charAt(i);

            // 3. 判断栈（待处理堆）的状态
            // 情况一：如果栈是空的，说明前面没有“邻居”，直接把当前字符放进去
            if(stack.empty()){
                stack.add(cur);
            } 
            // 情况二：如果栈不为空，并且栈顶字符（堆顶盘子）和当前字符不一样
            else if(cur != stack.peek()){
                // 说明它们不是一对，不能删，把当前字符也放进去
                stack.add(cur);
            } 
            // 情况三：如果栈不为空，并且栈顶字符和当前字符一样
            else{
                // 说明它们是一对相邻重复项！
                // 把栈顶的那个字符“拿出来”扔掉（pop），当前这个字符也不放进去了
                stack.pop();
            }
        }

        // 4. 遍历完所有字符后，栈里剩下的就是最终结果，但顺序是反的
        StringBuilder res = new StringBuilder();
        while (!stack.empty()){
            // 从栈顶开始取字符，第一个取到的是最后一个放入的
            res.append(stack.pop());
        }
        
        // 5. 因为是从栈顶开始取的，所以需要反转一下，才是正确的顺序
        return res.reverse().toString();
    }
}

关键点解释：