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

难度：🟢 简单

标签：栈、字符串

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

题目描述

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

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

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

示例 1：

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

解题思路

核心思想

本题的核心是消除所有相邻的重复字符。当我们遍历字符串时，需要一种能方便地访问“上一个未被消除的字符”的机制，以便与当前字符进行比较。这种“后进先出”的访问模式，正是 栈 数据结构的典型应用场景。

思路选择

栈法 是解决此问题的标准最优思路。

• 我们创建一个栈，用来存储最终结果字符串的字符。

• 遍历输入的字符串 s，对于每一个字符：

  • 查看栈顶元素。如果栈不为空且栈顶元素与当前字符相同，说明遇到了相邻的重复项，我们将栈顶元素弹出（即消除）。

  • 否则，就将当前字符压入栈中。

• 遍历结束后，栈中剩下的字符从栈底到栈顶组成的序列，就是消除所有重复项后的结果。

关键步骤

1. 初始化：创建一个空栈 stack（在 JavaScript 中可用数组模拟）。

2. 循环遍历：遍历输入字符串 s 中的每一个字符 char。

3. 比较与操作： a. 检查栈是否为空，以及栈顶元素 stack[stack.length - 1] 是否与当前字符 char 相等。 b. 如果相等，则从栈中弹出一个元素 stack.pop()。 c. 如果不相等（或栈为空），则将当前字符 char 压入栈中 stack.push(char)。

4. 返回结果：遍历结束后，将栈中的所有元素连接成一个字符串 stack.join('') 并返回。

代码实现

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicates = function (s) {
    const stack = [];

    for (const char of s) {
        // 如果栈顶元素与当前字符相同，则弹出
        if (stack.length > 0 && stack[stack.length - 1] === char) {
            stack.pop();
        } else {
            // 否则，压入新字符
            stack.push(char);
        }
    }

    return stack.join('');
};

复杂度分析

• 时间复杂度：O(n) 其中 n 是字符串 s 的长度。我们只需要对字符串进行一次完整的遍历。

• 空间复杂度：O(n) 在最坏的情况下（例如，字符串中没有重复项），我们需要将所有 n 个字符都压入栈中。

相关题目

• 0020.有效的括号

• 0155.最小栈

• 0739.每日温度

总结

本题是栈数据结构的经典应用之一。通过利用栈“后进先出”的特性，我们可以非常方便地访问和处理“最近的”未匹配字符，从而高效地解决了相邻项消除的问题。