• 时间：2022-05-25
• 题目序号：1047
• 难度：简单

问题描述

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

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

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

来源：力扣（LeetCode）

示例

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

提示

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

解题思路

题解部分参考自代码随想录。如有侵权，请联系进行删除~~

• 由题目内容我们可以知道：字符串是由纯字母组成，要删除的元素是相邻的
• 删除某元素后，后续元素继续前移，如果和被删除元素前的元素再次形成相邻重复，就继续删除，直到删除不了为止
• 本题我们可以用栈来解决

• 配合上面的动图，首先结合题目要求，了解要删除元素的特点
• 首先遍历字符串，当栈不为空或者栈顶元素和当前字符不等时，将其入栈
• 如果遍历的字符和栈顶元素相等，则将栈顶元素弹出（实现删除操作）
• 循环结束后，将栈内元素弹出并拼接，就是删除重复元素后的字符串

代码实现

class Solution {
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){        // 遍历字符串
            char ch = s.charAt(i);
            if(stack.isEmpty() || stack.peek() != ch){      // 符合条件入栈
                stack.push(ch);
            }else{      // 栈内元素和当前字符重复，弹出
                stack.pop();
            }
        }
        // 目前栈内元素即为去重后的元素，依次弹出并拼接
        String result = "";
        while(!stack.isEmpty()){
            result = stack.pop() + result;      // 注意顺序，pop在前，拼接在后
        }
        return result;
    }
}

总结

• 本题整体比较容易理解，需要注意的就是最后字符串拼接时，需要注意顺序，先pop，在拼接，否则最终顺序就是结果的逆序
• 在字符串拼接时，还可以进行优化，使用StringBuilder，因为在字符串使用+进行拼接时，底层就是使用StringBuilder的append方法，在拼接完后，使用reverse反转顺序即可