字符消消乐：消除相邻重复字符算法详解

最近遇到一个有趣的算法问题，类似于字符消消乐游戏，需要消除字符串中相邻的重复字符。这个问题看似简单，但实现起来却有不少细节需要考虑。本文将详细介绍这个问题的解法，并提供完整的Java实现代码。

问题描述

给定一个字符串，消除其中所有相邻的重复字符。类似于消消乐游戏，但只需要两个相同的相邻字符即可消除。例如：

• abbbaadeffc → dec
• abbbcdeffc → acdec

消除规则：

1. 从左到右扫描字符串
2. 遇到相邻重复字符时，消除所有这些重复字符
3. 消除后可能产生新的相邻重复，需要继续处理
4. 非相邻的重复字符不需要消除

算法思路

这个问题可以使用递归或栈来解决。本文采用递归方法，主要思路如下：

1. 遍历字符串，记录当前字符及其出现次数
2. 当遇到不同字符时，检查前一个字符是否重复
3. 如果重复，则消除这些字符，然后重新处理字符串
4. 如果没有重复，则继续处理下一个字符

代码实现

import java.util.ArrayList;
import java.util.List;

public class StringElimination {

    public static void main(String[] args) {
        String originalStr = "abbbaadeffc";
        // String originalStr = "abbbcdeffc";
        List<String> originalCharsList = new ArrayList<>();

        // 将字符串转换为字符列表
        for (int k = 0; k < originalStr.length(); k++) {
            originalCharsList.add(String.valueOf(originalStr.charAt(k)));
        }

        eliminateDuplicates(originalCharsList);
    }

    /**
     * 消除相邻重复字符的主方法
     * @param input 输入的字符列表
     */
    public static void eliminateDuplicates(List<String> input) {
        if (input == null || input.isEmpty()) {
            return;
        }

        int startIndex = 0;
        int repeatTimes = 0;
        String currentChar = "";

        for (int i = 0; i < input.size(); i++) {
            if (currentChar.isEmpty()) {
                currentChar = input.get(i);
                startIndex = i;
                repeatTimes = 1;
                continue;
            }

            if (currentChar.equals(input.get(i))) {
                repeatTimes++;
            } else {
                if (repeatTimes > 1) {
                    input = removeDuplicates(input, startIndex, repeatTimes);
                    eliminateDuplicates(input);
                    return;
                }
                currentChar = input.get(i);
                startIndex = i;
                repeatTimes = 1;
            }
        }

        if (repeatTimes > 1) {
            eliminateDuplicates(removeDuplicates(input, startIndex, repeatTimes));
        } else {
            // 输出最终结果
            StringBuilder result = new StringBuilder();
            for (String item : input) {
                result.append(item);
            }
            System.out.println(result.toString());
        }
    }

    /**
     * 移除指定范围内的重复字符
     * @param input 输入列表
     * @param startIndex 开始索引
     * @param repeatTimes 重复次数
     * @return 处理后的列表
     */
    private static List<String> removeDuplicates(List<String> input, int startIndex, int repeatTimes) {
        List<String> result = new ArrayList<>();
        for (int i = 0; i < input.size(); i++) {
            if (i < startIndex || i >= startIndex + repeatTimes) {
                result.add(input.get(i));
            }
        }
        return result;
    }
}

算法分析

时间复杂度

最坏情况下，每次只能消除一对字符，时间复杂度为O(n²)。平均情况下，时间复杂度接近O(n)。

空间复杂度

使用了额外的列表存储字符，空间复杂度为O(n)。

优化思路

可以使用栈来优化这个算法：

1. 初始化一个空栈
2. 遍历字符串中的每个字符
3. 如果栈不为空且栈顶元素等于当前字符，则弹出栈顶元素
4. 否则将当前字符压入栈中
5. 最后栈中剩余元素即为结果

栈实现示例

public static String eliminateWithStack(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (!stack.isEmpty() && stack.peek() == c) {
            stack.pop();
        } else {
            stack.push(c);
        }
    }
    StringBuilder sb = new StringBuilder();
    for (char c : stack) {
        sb.append(c);
    }
    return sb.toString();
}

测试用例

总结

本文介绍了消除相邻重复字符的算法，关键点包括：

1. 理解问题需求，明确消除规则
2. 选择合适的算法结构（递归或栈）
3. 处理边界条件和特殊情况
4. 考虑时间复杂度和空间复杂度

这个问题看似简单，但能很好地考察对字符串处理、递归和栈的理解。希望本文对你有所帮助，欢迎留言讨论更好的解决方案！