LeetCode刷题-删除字符串中的所有相邻重复项

前言说明

算法学习，日常刷题记录。

题目连接

题目内容

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

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

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

示例:

输入："abbaca"

输出："ca"

解释：

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

提示：

1 <= S.length <= 20000

S仅由小写英文字母组成。

分析过程

我们很容易就能想到用栈的方法来解决，而且相关标签也提示用栈。

当前元素和栈顶元素不同时，入栈。

当前元素和栈顶元素相同时，不入栈，并且出栈，这时就把重复项删除了。

所以如下代码：

class Solution {
    public String removeDuplicates(String s) {
        // 定义栈，保存不相邻重复的字符
        Stack<Character> stack = new Stack<>();

        // 遍历字符串s的字符
        for (int i = 0; i < s.length(); ++i) {
            if (stack.size() > 0) {
                // 若栈不为空，判断栈的顶部元素是否和当前字符相等
                if (stack.peek() == s.charAt(i)) {
                    // 若栈的顶部元素和当前字符相等，出栈，删掉了两个相邻重复的元素
                    stack.pop();
                } else {
                    // 若栈的顶部元素和当前字符不相等，字符入栈
                    stack.push(s.charAt(i));
                }
            } else {
                // 若栈为空，直接字符入栈
                stack.push(s.charAt(i));
            }
        }

        // 定义字符串集合
        StringBuilder sb = new StringBuilder();

        // 遍历栈的元素，从头到尾遍历
        for (Character character : stack) {
            // 把栈的元素保存到字符串集合
            sb.append(character);
        }
        
        // 字符串集合转为字符串，返回结果
        return sb.toString();
    }
}

但是提交后运行时间如下：

运行结果

执行用时28ms，时间击败39.22%的用户，内存消耗39.1MB，空间击败41.99%的用户。

运行时间和运行空间都不理想，但是我们看题目的提示就是说用栈来解决的啊，为什么运行结果这么不理想的？

后来我逛了一下评论区才发现，原来小丑是我，在LeetCode的讨论区有一个这样的评论，如下：

image.png

题目提示使用栈，你就真的乖乖地定义一个栈吗？

其实StringBuilder本身就可以模拟出栈的功能，何必多此一举去先定义一个栈，再遍历栈把栈的内容写入StringBuilder里呢？直接使用StringBuilder来保存元素就可以了。

解答代码

所以更节省时间和空间的代码如下：

class Solution {
    public String removeDuplicates(String s) {
        // 定义字符串集合
        StringBuilder sb = new StringBuilder();

        // 定义字符串集合最外元素的下标
        int top = -1;

        // 遍历字符串s的字符
        for (int i = 0; i < s.length(); ++i) {
            if (top >= 0 && sb.charAt(top) == s.charAt(i)) {
                // 若字符串集合的最外元素和当前字符相等，删除最外元素，并且字符不保存进字符串集合
                sb.deleteCharAt(top);
                // 字符串集合最外元素的下标减1
                --top;
            } else {
                // 若字符串集合的最外元素和当前字符不相等，字符保存进字符串集合
                sb.append(s.charAt(i));
                // 字符串集合最外元素的下标加1
                ++top;
            }
        }
        
        // 字符串集合转为字符串，返回结果
        return sb.toString();
    }
}

提交结果

执行用时13ms，时间击败77.58%的用户，内存消耗39MB，空间击败67.16%的用户。