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

发表于 更新于 分类于

算法-删除字符串中的所有相邻重复项

背景

  • 算法–删除字符串中的所有相邻重复项

  • 博主以代码随想录算法公开课进行学习

题目

  • 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

    在 S 上反复执行重复项删除操作，直到无法继续删除。

    在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

    示例：

    • 输入：“abbaca”
    • 输出：“ca”
    • 解释：例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。

    提示：

    • 1 <= S.length <= 20000
    • S 仅由小写英文字母组成

思路

  • 核心逻辑：利用栈的「后进先出」特性处理相邻重复项——遍历字符串时，用栈存储未重复的字符，当前字符与栈顶相同则弹出栈顶（删除重复项），不同则压入栈；
  • 具体步骤：
    • 初始化栈，遍历字符串每个字符：
      • 若栈为空 或 当前字符 ≠ 栈顶字符 → 压入栈（无重复，保留字符）；
      • 若当前字符 = 栈顶字符 → 弹出栈顶（删除相邻重复项）；
    • 遍历结束后，栈中剩余字符即为「无相邻重复的最终字符串」，按顺序拼接即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public String removeDuplicates(String s) {
        // 用ArrayDeque模拟栈（效率高于Stack）
        ArrayDeque<Character> deque = new ArrayDeque<>();
        char ch;
         // 遍历字符串每个字符
        for(int i = 0;i<s.length();i++){
            ch = s.charAt(i);
             // 栈空 或 当前字符≠栈顶 → 压入栈
            if(deque.isEmpty()||deque.peek() != ch){
                deque.push(ch);
            }else{
                // 当前字符=栈顶 → 弹出栈顶（删除重复项）
                deque.pop();
            }
        }
         // 拼接栈中剩余字符（栈是倒序，需从栈底到栈顶拼接）
        String str = "";
        while(!deque.isEmpty()){
            // 每次取栈顶拼接到字符串前面，保证顺序正确
            str = deque.pop() + str;
        }
        return str;
    }
}

总结

  • 栈的经典应用：相邻重复项的删除符合「后进先出」逻辑 —— 最新遍历的字符需与「最近未重复的字符（栈顶）」匹配，栈天然适配这种场景；
  • 效率优势：相比「暴力遍历 + 反复删除」（时间复杂度 O (n²)），栈解法仅需一次遍历（O (n)），是最优解；