如何生成长度不超过6的唯一字母组合并优化Spelling Bee匹配程序

前两个优化目标的实现逻辑 #

你的两个优化需求本质上是把原来的排列遍历改成组合遍历，总遍历量从原来的26^7≈80亿次降到26*C(25,6)≈460万次，性能提升三个数量级以上：

1. 针对优化2：遍历每个必填字符时，先从字母表中过滤掉该必填字符，生成大小为25的可选字符池，从根源避免可选字符包含必填字符。
2. 针对优化1：从25个可选字符中生成6个字符的无重复升序组合（即索引满足i0 < i1 < i2 < i3 < i4 < i5），既保证不会出现重复字母的组合，也不会出现内容相同顺序不同的雷同组合，每个组合只会被测试一次。

优化后代码实现 #

int numMaxSolutions = 0;
char[] alphabet = "abcdefghijklmnopqrstuvwxyz".toCharArray();
// 预先过滤长度不符合要求的单词，减少后续循环匹配次数
List<String> validLengthWords = words.stream()
        .filter(word -> word.length() >= minLength)
        .toList();

for (char keyChar : alphabet) {
    // 生成排除必填字符的可选池，满足优化2要求
    List<Character> candidatePool = new ArrayList<>();
    for (char c : alphabet) {
        if (c != keyChar) candidatePool.add(c);
    }
    int poolSize = candidatePool.size();

    // 生成25选6的无重复升序组合，满足优化1要求
    for (int i0 = 0; i0 < poolSize - 5; i0++) {
        for (int i1 = i0 + 1; i1 < poolSize - 4; i1++) {
            for (int i2 = i1 + 1; i2 < poolSize - 3; i2++) {
                for (int i3 = i2 + 1; i3 < poolSize - 2; i3++) {
                    for (int i4 = i3 + 1; i4 < poolSize - 1; i4++) {
                        for (int i5 = i4 + 1; i5 < poolSize; i5++) {
                            char[] optionalChars = new char[]{
                                    candidatePool.get(i0),
                                    candidatePool.get(i1),
                                    candidatePool.get(i2),
                                    candidatePool.get(i3),
                                    candidatePool.get(i4),
                                    candidatePool.get(i5)
                            };
                            Pattern pattern = constructPattern(keyChar, optionalChars);
                            List<String> results = new ArrayList<>();
                            for (String word : validLengthWords) {
                                if (pattern.matcher(word).matches()) {
                                    results.add(word);
                                }
                            }
                            if (results.size() > numMaxSolutions) {
                                numMaxSolutions = results.size();
                                System.out.printf("Max: %c-%s (%d)%n", keyChar, String.valueOf(optionalChars), numMaxSolutions);
                            }
                        }
                    }
                }
            }
        }
    }
}

额外优化方向 #

还可以做以下优化进一步提升性能：

• 用位掩码替代正则匹配：提前给每个符合长度要求的单词生成26位整数掩码，每个bit对应一个字母是否在单词中出现。判断时仅需两个位运算：单词掩码包含必填字符的bit，且没有超出允许字符范围的bit，速度比正则快至少2个数量级。
• 提前统计字母出现频率，优先测试高频字母组成的组合，可以更快找到高匹配量的最优解，不需要全量遍历的场景下可以提前终止。
• 如果需要全量遍历，可以把匹配逻辑改成按组合统计：预先给每个单词生成掩码后，直接统计每个符合规则的7字母组合（1个必填+6个可选）对应的单词数，避免每个组合都遍历一次单词库。

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