删除字符串中的所有相邻重复项
【题目】给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。本题对应于leetcode 1047
示例：
- 输入："abbaca"
- 输出："ca"
- 解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
提示：
- 1 <= S.length <= 20000
- S 仅由小写英文字母组成。
【思路】
第一种方法的思路我也想到了，就是在最后字符串的拼接操作出现了问题，没有完整的写出来。
本题也是用栈来解决的经典问题。
代码实现如下：
class Solution { public String removeDuplicates(String s) { //ArrayDeque会比LinkedList在除了删除元素这一点外会快一点 //参考：https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist ArrayDeque<Character> deque = new ArrayDeque<>(); char ch; for (int i = 0; i < s.length(); i++) { ch = s.charAt(i); // stack不为空并且当前字符和栈顶元素相同，则栈顶元素出栈 if (!stack.isEmpty() && ch == stack.peek()) { stack.pop(); } else { stack.push(ch); } } String new_s = ""; // stack中的元素和目标元素正好是反过来的，直接每次在new_s之前做拼接操作，最后得到的就是目标结果 while(!stack.isEmpty()) { new_s = stack.pop() + new_s; } return new_s; } }
方法二
class Solution { public String removeDuplicates(String s) { // 方法二：直接拿字符串当栈来用 // 将res当做栈 // 也可以用StringBuilder来修改字符串,速度更快 StringBuffer res = new StringBuffer(); // top为res的长度 int top = -1; for (int i = 0; i < s.length(); ++i) { char c = s.charAt(i); // 当top>0，即栈中有字符时，当前字符如果和栈中字符相等，弹出栈顶字符，同时top-- if (top >= 0 && res.charAt(top) == c) { res.deleteCharAt(top); top--; // 否则,将该字符入栈,同时top++ } else { res.append(c); top++; } } return res.toString(); } }
