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}
总结
这题使用栈是最容易想到的，每次只需要比较要入栈的值和栈顶元素即可，如果一样，就同时消失。当然还可以使用双端队列，他是两头都可以添加和删除的一种数据结构，具体可以看下359，数据结构-3,队列