【百日算法计划】：每日一题，见证成长（020）

题目

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

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
输入：“abbaca”
输出：“ca”

思路

• 栈的解法，判断字符与栈顶元素是否相等，相等则弹出栈顶元素，否则将字符押入栈（注意：不需要构造对象计数）

public class Code09 {//栈解法public String removeDuplicates(String s) {if (s == null) return null;Stack<Character> stack = new Stack<>();int n = s.length();for (int i = 0; i < n; i++) { //顺序处理每个字符char c = s.charAt(i);if (!stack.isEmpty() && c == stack.peek()){stack.pop();} else {stack.push(c);}}int size = stack.size();char[] chars = new char[size];for (int i = size-1; i >= 0; i--) {chars[i] = stack.pop();}String s1 = String.valueOf(chars);return s1;}   
}