如何优化生成逗号分隔数字列表算法的时间复杂度？

问题说明 #

输入数字格式的字符串，需要生成所有合法的逗号分隔字符串列表，核心要求是结果中不能包含3位及以上的连续数字。示例如下：

• 输入："1" → 输出：["1"]
• 输入："12" → 输出：["12", "1,2"]
• 输入："123" → 输出：["1,23", "12,3", "1,2,3"]

原代码的性能瓶颈 #

你当前实现的代码通过枚举所有可能的分隔组合（共2^{(n-1)种），再用正则过滤无效结果，时间复杂度约为O(2}n * n)。当输入字符串较长时，会生成大量无效组合，导致性能严重下降。

优化方案：递归回溯（提前剪枝） #

按照你设想的思路，我们可以通过递归回溯，在生成过程中直接避开会产生3位连续数字的分支，不用等到最后再过滤。关键是跟踪当前生成字符串的末尾数字段长度：

• 如果当前末尾数字段已经有2位，下一个字符必须加逗号分隔（否则会形成3位连续数字，违反规则）
• 如果当前末尾数字段是1位，下一个字符有两种选择：直接追加（变成2位数字段），或者加逗号后追加（新的1位数字段）
• 如果当前字符串以逗号结尾（即刚完成一次分隔），下一个字符直接追加（形成新的1位数字段）

实现代码 #

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

public class CommaSeparator {
    public static List<String> getCommaSeparatedNumbers(String num) {
        List<String> results = new ArrayList<>();
        if (num == null || num.isEmpty()) {
            return results;
        }
        // 初始调用：从第一个字符开始，当前末尾数字段长度为1
        backtrack(num, 1, new StringBuilder(num.substring(0, 1)), results);
        return results;
    }

    /**
     * 递归回溯生成合法字符串
     * @param num 原始数字字符串
     * @param pos 当前处理到的字符索引（从1开始）
     * @param current 当前正在构建的字符串
     * @param results 结果列表
     */
    private static void backtrack(String num, int pos, StringBuilder current, List<String> results) {
        if (pos == num.length()) {
            results.add(current.toString());
            return;
        }

        char nextChar = num.charAt(pos);
        int lastSegmentLength = getLastDigitSegmentLength(current);

        // 情况1：如果末尾数字段长度小于2，可以直接追加字符（不加分隔符）
        if (lastSegmentLength < 2) {
            current.append(nextChar);
            backtrack(num, pos + 1, current, results);
            current.deleteCharAt(current.length() - 1); // 回溯
        }

        // 情况2：无论当前末尾数字段长度是多少，都可以加分隔符后追加字符
        current.append(",").append(nextChar);
        backtrack(num, pos + 1, current, results);
        current.delete(current.length() - 2, current.length()); // 回溯：删除逗号和刚加的字符
    }

    /**
     * 获取当前字符串末尾的数字段长度
     */
    private static int getLastDigitSegmentLength(StringBuilder sb) {
        int count = 0;
        for (int i = sb.length() - 1; i >= 0; i--) {
            if (Character.isDigit(sb.charAt(i))) {
                count++;
            } else {
                break;
            }
        }
        return count;
    }
}

代码说明 #

• backtrack方法负责递归构建字符串，每次处理下一个字符时，根据当前末尾数字段的长度决定可选的分支
• getLastDigitSegmentLength辅助方法快速获取当前字符串末尾连续数字的长度，用于判断后续操作
• 回溯操作会撤销当前的选择，确保所有合法分支都被遍历到

这种方法只会生成符合要求的组合，避免了无效组合的生成，时间复杂度大幅降低，尤其是对于长字符串，性能提升非常明显。

内容的提问来源于stack exchange，提问作者Eren