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

Original 博哥数据结构和算法 2022-05-19

收录于合集 #算法图文分析 161个

It may not be pretty, but we headed to the city.

其貌虽不扬，扬帆亦远航。

问题描述

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

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

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

示例：

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

提示：

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

使用栈解决

这题让把挨着的并且相同的字符同时给删除，最简单的实现方式就是使用栈来解决。

我们遍历字符串中的所有字母：

1，如果栈为空

就把当前字母加入到栈中。

2，如果栈不为空

如果当前字母等于栈顶元素，说明他俩是相邻且相同的，让他俩同时消失。
如果当前字母不等于栈顶元素，说明他俩是相邻但不相同，直接让当前字母入栈。

具体以示例为例来看下视频

上面视频中是先入栈之后，如果两个有相同的在同时消失，其实我们不需要先入栈，而是先比较，如果相同让栈顶元素出栈即可，来看下代码

 1public String removeDuplicates(String S) {
 2    char[] chars = S.toCharArray();
 3    Stack<Character> stack = new Stack<>();
 4    int index = 0;
 5    int length = S.length();
 6    while (index < length) {
 7        char current = chars[index++];
 8        if (!stack.empty() && stack.peek() == current) {
 9            //如果栈顶的值和当前遍历的值相同，他两直接消失
10            stack.pop();
11        } else {
12            //如果栈为空，或者栈顶元素和当前值不相同，就把当前值压入栈
13            stack.push(current);
14        }
15    }
16    //下面是把栈中的元素转化为字符串
17    StringBuilder stringBuilder = new StringBuilder(stack.size());
18    while (!stack.empty())
19        stringBuilder.append(stack.pop());
20    return stringBuilder.reverse().toString();
21}

使用双指针解决

大家应该都玩过连连看吧，就是挨着的多个相同的会同时消失。我们这里类似于连连看，挨着两个相同的同时消失，可以使用两个指针。

一个right一直往右移动，然后把指向的值递给left指向的值即可。
一个left每次都会比较挨着的两个是否相同，如果相同，他两同时消失。

具体看下视频

代码如下

 1public String removeDuplicates(String S) {
 2    int left = 0;
 3    int right = 0;
 4    int length = S.length();
 5    char[] chars = S.toCharArray();
 6    while (right < length) {
 7        //先把右边的字符赋值给左边
 8        chars[left] = chars[right];
 9        //然后判断左边挨着的两个字符是否相同，如果相同，
10        //他两同时消失，也就是left往回退两步
11        if (left > 0 && chars[left - 1] == chars[left])
12            left -= 2;
13        ++right;
14        ++left;
15    }
16    return new String(chars, 0, left);
17}

还可以使用StringBuilder，原理都是一样的，来看下代码

 1public String removeDuplicates(String S) {
 2    StringBuilder stringBuilder = new StringBuilder();
 3    char[] chars = S.toCharArray();
 4    for (char ch : chars) {
 5        int size = stringBuilder.length();
 6        if (size > 0 && stringBuilder.charAt(size - 1) == ch) {
 7            stringBuilder.deleteCharAt(size - 1);
 8        } else {
 9            stringBuilder.append(ch);
10        }
11    }
12    return stringBuilder.toString();
13}