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

描述

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

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

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

示例：

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

提示：

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

题解

C++：

class Solution {
public:
    string removeDuplicates(string S) {
        stack<char> stk; // 定义一个栈
        for (char c : S) { // 遍历字符串中的每一个字符
            if (!stk.empty() && stk.top() == c) { // 如果栈不为空且栈顶元素等于当前字符
                stk.pop(); // 弹出栈顶元素
            } else {
                stk.push(c); // 否则将当前字符压入栈中
            }
        }
        string ans = "";
        while (!stk.empty()) { // 遍历栈中的元素
            ans += stk.top(); // 将栈顶元素加入到答案字符串中
            stk.pop(); // 弹出栈顶元素
        }
        reverse(ans.begin(), ans.end()); // 翻转答案字符串
        return ans; // 返回答案字符串
    }
};

该算法的时间复杂度为 $O(n)$，其中 $n$ 表示字符串的长度。算法的空间复杂度为 $O(n)$，其中 $n$ 表示字符串的长度。

算法的具体步骤如下：

1. 定义一个栈，用于存储没有重复的字符。
2. 遍历字符串中的每一个字符，如果栈不为空且栈顶元素等于当前字符，则弹出栈顶元素；否则将当前字符压入栈中。
3. 遍历栈中的元素，将栈顶元素加入到答案字符串中，并弹出栈顶元素。
4. 翻转答案字符串，得到最终的结果。

例如，当输入字符串为 “abbaca” 时，该算法的执行过程如下：

1. 初始化栈为空。
2. 遍历字符串中的每一个字符：
   • 当前字符为 ‘a’，将 ‘a’ 压入栈中，栈中的元素为 {a}。
   • 当前字符为 ‘b’，将 ‘b’ 压入栈中，栈中的元素为 {a, b}。
   • 当前字符为 ‘b’，弹出栈顶元素 ‘b’，栈中的元素为 {a}。
   • 当前字符为 ‘a’，弹出栈顶元素 ‘a’，栈为空。
   • 当前字符为 ‘c’，将 ‘c’ 压入栈中，栈中的元素为 {c}。
   • 当前字符为 ‘a’，将 ‘a’ 压入栈中，栈中的元素为 {c, a}。
3. 遍历栈中的元素：
   • 将栈顶元素 ‘a’ 加入到答案字符串中，栈中的元素为 {c}。
   • 将栈顶元素 ‘c’ 加入到答案字符串中，

Python：

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []
        for c in s:
            if len(stack)!=0 and c == stack[-1]:
                stack.pop()
            else:
                stack.append(c)
        ans = "".join(stack) # 转为字符串
        return ans