力扣 1047. 删除字符串中的所有相邻重复项

题目说明

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

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

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

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

示例

例1

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

笔者理解

此题是一道字符串算法问题，在力扣题库中被定义为简单题。

解法

当笔者阅读完此题后，发现此题很适合用栈，然后将字符串各个字母存进栈中，相同的就弹出来，输出最后留在栈中的字母即可，但后来发现这样的时间和空间效率都不高，在评论里发现一种巧妙的方法，用一个标记tick来标记当前的栈（非真实定义的栈）内元素有几个，然后通过i的移动来判断当前元素是否应该入栈，应该入栈就将元素置换到前面去，最后再将前tick+1个元素转化为字符串输出即可，让我们来看看具体如何实现的吧。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public String removeDuplicates(String S) {
        if(S.length()==1){ return S; }
        //当只有一个字母时，直接返回原字符串

        char []temp = S.toCharArray();
        //将字符串转化为字节数组，在字节数组中操作

        int tick = -1;
        //标记当前要操作的下标

        for(int i = 0; i < temp.length; i++) {
            if(tick >= 0 && temp[tick] == temp[i]) {
                tick--;
                //当标记在数组范围中，而且标记对应的字母和当前遍历的字母相同时
                //标签回退
            }
            else{
                tick++;
                temp[tick] = temp[i];
                //否则就将标签前置，并将标签对应的字母换成当前遍历的字母
                //即在字节数组中操作，用数组和标记来代替栈的元素入栈及相同元素出栈
                //tick代表着栈中有几个元素，i代表后续要操作的元素
            }
        }
        return String.valueOf(temp,0,tick+1);
        //截取字节数组0到tick+1的字节组成字符串并返回
    }

时间和空间效率都不错，可见此解法还比较适合此题；

image.png

总结

本题是今天的每日一题，难度是简单，感兴趣的朋友都可以去尝试一下，此题还有其他更多的解法，朋友们可以自己逐一尝试。