题目

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

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

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

public class DayCode {
    public static void main(String[] args) {
        String s = "abbaca";
        String ans = new DayCode().removeDuplicates(s);
        System.out.println("ans is " + ans);
    }
    /**
     * 时间复杂度O(n)
     * 空间复杂度O(n)
     * https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/
     * @param S
     * @return
     */
    public String removeDuplicates(String S) {
        StringBuilder stringBuilder = new StringBuilder();
        int n = S.length();
        Deque<Character> deque = new ArrayDeque<>(n);
        for (int i = 0; i < n; i++) {
            if (deque.isEmpty() || (!deque.isEmpty() && S.charAt(i) != deque.peek())) {
                deque.push(S.charAt(i));
            } else {
                while (!deque.isEmpty() && S.charAt(i) == deque.peek()) {
                    deque.pop();
                }
            }
        }
        while (!deque.isEmpty()) {
            stringBuilder.append(deque.pop());
        }
        return stringBuilder.reverse().toString();
    }
}

总结

* 这是一道简单题，重拳出击！题目含义容易理解。采用栈的数据结构，可以帮助简化问题，对栈进行添加，移除操作，最后返回字符串即可。

* 坚持每日一题，加油！