各位题友大家好！今天是 @负雪明烛 坚持日更的第 44 天。今天力扣上的每日一题是「1047. 删除字符串中的所有相邻重复项」。

解题思路

本题要点：
1. 两个相邻且相同字符会被删除。（注意：是两个！）
2. 删除字符串中两个相邻并且相同的字符可能会产生新的相邻并且相同的字符。比如对于 abba ，删除 bb 之后， aa 会碰到一起，也需要继续把 aa 删掉。

所以：

① 并不能一次删除操作就能达到目的；而应该在每次删除一对相邻且相同的字符之后、再看新的字符串是否存在相邻且相同的一对字符。
- ② 如果存在多组的相邻且相同的字符时，先删除哪一对对最终结果是没有影响的。比如对于 abbacca ，无论先删除 bb 还是先删除 cc 最终的结果都是 a 。

通过 ① 我们得出：需要用一个数据结构缓存结果，这个数据结构应该是后进先出，也就是栈！
通过 ② 我们得出：可以从左到右遍历一次输入字符串 S 的所有字符 Si，把 Si 跟栈顶元素比较，处理流程如下：

如果 Si 和栈顶元素相同，则说明他们是 直接相邻且相同 或者由于中间元素被删除导致的 间接相邻且相同，因此 Si 不入栈，并且要把栈顶元素弹出；
- 如果 Si 和栈顶元素不同，则说明它们两个无法被消除，则把 Si 入栈。

具体的操作流程如下面的 PPT 所示：

doing…

代码

提供了 Python, C++, Java 三种语言的代码。其中 C++ 代码没有直接使用栈，因为 std::string 本身就支持在字符串的末尾添加或者删除一个元素，类似于栈。

class Solution(object):
    def removeDuplicates(self, S):
        stack = []
        for c in S:
            if stack and c == stack[-1]:
                stack.pop()
            else:
                stack.append(c)
        return "".join(stack)

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

class Solution {
    public String removeDuplicates(String S) {
        Stack<Character> st = new Stack<>();
        for (int i = 0; i < S.length(); i++) {
            if (!st.empty() && S.charAt(i) == st.peek()) {
                st.pop();
            } else {
                st.add(S.charAt(i));
            }
        }
        StringBuilder res = new StringBuilder();
        for (Character c : st) {
            res.append(c);
        }
        return res.toString();
    }
}

时间复杂度：$O(N)$，因为对输入字符串 S 遍历了一次。
空间复杂度：$O(N)$，因为最坏情况下，栈的大小会与输入字符串 S 的大小相等。

刷题心得

对于一般的 Easy 和 Medium 题目，其实只有一个考察点，本题的考察点就是栈。

OK，以上就是 @负雪明烛写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！

算法每日一题题解

【每日一题】1047. 删除字符串中的所有相邻重复项

解题思路

代码

刷题心得