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

Categories:

题目描述
思路分析
1. 解法一：栈模拟（推荐）
相似题目

题目描述

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

思路分析

解法一：栈模拟（推荐）

核心思路：

遍历字符串中的每个字符，维护一个栈作为”结果缓冲区”。

若当前字符与栈顶字符相同，则弹出栈顶（相当于消除这对相邻重复字符）；否则将当前字符压栈。

遍历结束后，栈中保存的字符序列即为最终结果，直接转换为字符串返回。

关键点：利用栈的 LIFO 特性，每次入栈前检查是否与栈顶相同，实现”消消乐”式的连锁消除。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串的长度，每个字符至多入栈、出栈各一次。

空间复杂度：O(n)，其中 n 表示字符串的长度，最坏情况下（无相邻重复）栈中存储全部字符。

class Solution {
    public String removeDuplicates(String s) {
        StringBuilder stack = new StringBuilder();

        for (char c : s.toCharArray()) {
            // 栈顶字符与当前字符相同，弹出（消除相邻重复对）
            if (stack.length() > 0 && stack.charAt(stack.length() - 1) == c) {
                stack.deleteCharAt(stack.length() - 1);
            } else {
                // 不相同则将当前字符压栈
                stack.append(c);
            }
        }

        return stack.toString();
    }
}

func removeDuplicates(s string) string {
    stack := []byte{}

    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)
}

相似题目

题目	难度	考察点
1209. 删除字符串中的所有相邻重复项 II	中等	栈 / K 个相邻重复消除
844. 比较含退格的字符串	简单	栈 / 模拟退格
20. 有效的括号	简单	栈 / 配对消除
394. 字符串解码	中等	栈 / 字符串处理
316. 去除重复字母	中等	单调栈 / 贪心
735. 小行星碰撞	中等	栈 / 碰撞模拟
2390. 从字符串中移除星号	中等	栈 / 字符串消除

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/58637969