【LeetCode】删除字符串中的所有相邻重复项 Java 题解

HQ数字卡

关注

发布于: 2021 年 03 月 09 日

题目

给出由小写字母组成的字符串 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();    }}

复制代码

总结

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

发布于: 2021 年 03 月 09 日阅读数: 9

原文链接:【http://xie.infoq.cn/article/dc614296dfe81e9af9cd78b65】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】删除字符串中的所有相邻重复项 Java 题解

题目

代码

总结

HQ数字卡

评论