Easy

题目描述

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

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

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

示例 1：

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

示例 2：

输入：s = "azxxzy"
输出："ay"

提示：

  • 1 <= s.length <= 10^5
  • s 仅由小写英文字母组成。

解题思路

解题思路

这道题要求我们删除字符串中所有相邻的重复字符，直到无法再删除为止。我们可以用栈来高效解决这个问题。

栈的解法（推荐）：

  1. 遍历字符串中的每个字符
  2. 如果栈为空，或者当前字符与栈顶字符不相同，将当前字符压入栈
  3. 如果当前字符与栈顶字符相同，说明找到了相邻重复项，将栈顶字符弹出（相当于删除这一对重复字符）
  4. 最后栈中剩余的字符就是结果

这种方法的巧妙之处在于，当我们遇到重复字符时，通过弹出栈顶元素来模拟删除操作。由于栈的后进先出特性，这样可以正确处理连续的删除操作。

字符串模拟解法： 也可以直接使用字符串来模拟栈的行为，不断检查字符串末尾是否与当前字符相同。

时间复杂度为 O(n)，空间复杂度为 O(n)，其中 n 是字符串长度。

代码实现

class Solution {
public:
    string removeDuplicates(string s) {
        string result;
        for (char c : s) {
            if (!result.empty() && result.back() == c) {
                result.pop_back();
            } else {
                result.push_back(c);
            }
        }
        return result;
    }
};

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []
        for c in s:
            if stack and stack[-1] == c:
                stack.pop()
            else:
                stack.append(c)
        return ''.join(stack)

public class Solution {
    public string RemoveDuplicates(string s) {
        var result = new System.Text.StringBuilder();
        foreach (char c in s) {
            if (result.Length > 0 && result[result.Length - 1] == c) {
                result.Remove(result.Length - 1, 1);
            } else {
                result.Append(c);
            }
        }
        return result.ToString();
    }
}

var removeDuplicates = function(s) {
    const stack = [];
    for (const c of s) {
        if (stack.length > 0 && stack[stack.length - 1]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串一次，每个字符最多入栈出栈一次
空间复杂度O(n)最坏情况下栈需要存储所有字符

相关题目