一、题目描述

原文链接：1047. 删除字符串中的所有相邻重复项

具体描述：
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。

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

示例：

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

提示：

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

二、思路分析

这道题有意思喽，三种方式！
方式一：用栈来解决

• 定义一个栈stack
• 遍历字符串，依次添加元素到栈当中
• 如果栈不为空，并且栈顶元素和当前遍历的字符相等则弹出栈顶，不进行添加
• 最后遍历结束，如果栈元素为空，则说明配对成功，否则配对失败！

方式二：用ArrayDeque，它其实也是栈，也是队列，也是双端队列，就看调用的方法而已！解决思路跟上面一样，看看代码即可！

方式三：就是用StringBuilder来模拟栈

• 定义个StringBuilder来存储元素和下标索引从-1开始！ StringBuilder sb = new StringBuilder(); int index = -1;//sb的索引
• 遍历字符串，如果索引大于0,并且当前元素等于索引对应的元素，则删除该字符
• 否则吧该字符添加到sb当中
• 最后如果sb为空，则说明配对成功，否则配对失败！

三、AC代码

方式一：栈

class Solution {    public String removeDuplicates(String s) { Stack<Character> stack = new Stack<>(); for (char c : s.toCharArray()){     if (stack.empty() == false && stack.peek() == c){  stack.pop();     }else {  stack.push(c);     } } StringBuilder sb = new StringBuilder(); while (!stack.empty()){     sb.append(stack.pop()); } return sb.reverse().toString();    }}

方式二：双端队列

class Solution {    public String removeDuplicates(String s) {// 它可以为堆，也可是是栈，更可以当作双端队列Deque<Character> deque = new ArrayDeque<>();for (char c : s.toCharArray()){    if (deque.isEmpty() == false && deque.peek() == c){ deque.pop();    }else{ deque.push(c);    }} StringBuilder sb = new StringBuilder();while (!deque.isEmpty()){    sb.append(deque.pop());}return sb.reverse().toString();    }}

方式三：StringBuilder模拟栈

class Solution {    public String removeDuplicates(String s) {StringBuilder sb = new StringBuilder();int index = -1;//sb的索引for (char c : s.toCharArray()){    if (index >= 0 && sb.charAt(index) == c){ sb.deleteCharAt(index); index--;    }else{ sb.append(c); index++;    }}return sb.toString();    }}

四、总结

• ArrayDeque即可以是栈，也可以是队列，更可以是双端队列！

感谢大家的阅读，我是Alson_Code，一个喜欢把简单问题复杂化，把复杂问题简单化的程序猿！ ❤