算法：删除字符串中的所有相邻重复项-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法：删除字符串中的所有相邻重复项。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

一、问题描述

二、栈解法

三、双指针解法

总结

提示：以下是本篇文章正文内容，下面案例可供参考

一、问题描述

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

输入："abbaca"
输出："ca"

str 仅由小写英文字母组成

二、栈解法

解题思路：

可以将要比较的对象压栈，然后用将要比较的对象和栈顶元素比较，相同的话，栈顶元素出栈，不相同，则把将要比较的对象入栈，作为新的栈顶元素。当栈顶元素弹出后，前一个元素就变成了新的栈顶元素。

代码示例：

public void test() {
    // 存储遍历到不相同的字符
    Stack<Character> stack = new Stack<>();
    String str = "abbaca";
    int i = 0;
    while(i++ < str.length()) {
        // 从第一个字符开始
        char charAt = str.charAt(i - 1);
        // 如果栈是空的或者当前字符与栈顶元素不相同, 则入栈, 要注意, stack的peek操作, 如果栈是空的则抛异常
        if (stack.isEmpty() || !Objects.equals(charAt, stack.peek())) {
            stack.push(charAt);
            continue;
        }
        // 如果栈非空且当前字符与栈顶元素相同, 则出栈
        stack.pop();
    }
    StringBuffer sb = new StringBuffer();
    while(!stack.isEmpty()) {
        sb.append(stack.pop());
    }
    // 字符反转, 并输出
    System.out.println(sb.reverse());
}

三、双指针解法

解题思路：

对于对称的字符串来说，有一个规律，从中间开始，向左移动一位和向右移动一位的元素是相同的，可以成对的删除。正常情况下，每次左右指针都从同一个位置出发，然后右指针先行一步，然后再对比两个指针元素的值。这个过程中有特殊情况需要处理，首先是左指针已经移动到头了；其次是怎么删除元素。因为在整个过程中，有可能删除的是整个字符串的某些部分，然后就将字符串分割为好几段，最终我们需要的恰恰又是一个完整的字符串。

代码示例：

public void test() {
    int left = 0;
    int right = 0;
    String str = "abbaca";
    char[] chars = str.toCharArray();
    while(right < str.length() - 1) {
        // 右指针向右移动, 和left拉开距离
        right++;
        // 如果值相同, 则进行删除
        if (chars[right] == chars[left]) {
            // 对应位置打标记, 随后删除
            chars[right] = 0;
            // 对应位置打标记, 随后删除
            chars[left] = 0;
            // 如果left已经到左边尽头了, 则重置left, 将left设为和right一样的起点
            if (left == 0) {
                left = ++right;
                continue;
            }
            // left未到左边尽头, left向左移动一位
            left = left - 1;
            continue;
        }
        // 元素不相同, left向右移动, 和right保持相同的起始位置
        left = right;
    }
    // 最终输出的内容里, 替换掉标记
    System.out.println(JSON.toJSONString(chars).replace("\\u0000", ""));
}