如何优化含空白tiles的Scrabble单词组合生成代码？

问题概述 #

开发Scrabble最优解工具时，需实现以下需求：

• 给定含空白牌_的字母集合，生成所有可能的单词组合（无需词典验证）
• 空白牌可替换为任意有效字母，生成的单词中空白替换的字母用大写标识，原生字母保留小写
• 移除存在对应小写版本的大写单词（即某大写单词转小写后可由原生字母直接生成，则丢弃该大写单词）
• 支持多空白牌场景

当前实现在5个原生字母+2个空白牌的场景下耗时超1分钟，核心瓶颈在去重环节，且原去重函数存在功能错误，需优化算法解决性能与功能问题。

原代码核心问题 #

1. 标识混淆：将所有字母（原生+空白替换）统一转大写，无法区分空白生成的单词，导致去重逻辑无法正确执行
2. 生成冗余：未对排列结果去重，相同字母组合的重复排列会被多次生成，大幅增加后续处理量
3. 去重低效：采用排序+二分查找的方式，时间复杂度为O(n log n)，且逻辑错误，无法准确过滤目标单词

核心优化思路 #

1. 区分原生与空白字母：原生字母保留小写，空白替换字母用大写，从根源上区分两类单词
2. 减少重复生成：用集合去重排列结果，避免相同字母组合生成重复排列；空白替换用combinations_with_replacement避免重复的替换组合
3. 哈希集合快速查询：用集合存储所有原生小写单词，过滤大写单词时直接O(1)查询是否存在对应小写，替代低效的排序+二分查找

重构后的代码 #

import itertools
import time

def find_all_word_combinations(letters, wild_card='_', valid_letters='abcdefghijklmnopqrstuvwxyzæøå'):
    # 拆分原生字母（小写）和空白牌数量
    native_letters = [c.lower() for c in letters if c != wild_card]
    blank_count = letters.count(wild_card)
    valid_upper = valid_letters.upper()

    # 生成所有原生字母能组成的单词（全小写），用集合去重
    native_words = set()
    n_len = len(native_letters)
    for length in range(1, n_len + 1):
        for combo in itertools.combinations(native_letters, length):
            native_words.update(''.join(p) for p in itertools.permutations(combo))

    # 处理空白牌生成的单词（含大写字母）
    blank_generated_words = set()
    if blank_count > 0:
        # 生成所有空白替换的字母组合（避免重复组合）
        for blank_letters in itertools.combinations_with_replacement(valid_upper, blank_count):
            combined = native_letters + list(blank_letters)
            c_len = len(combined)
            for length in range(1, c_len + 1):
                for combo in itertools.combinations(combined, length):
                    for perm in itertools.permutations(combo):
                        word = ''.join(perm)
                        # 仅保留用到空白牌的单词（含大写）
                        if any(c.isupper() for c in word):
                            blank_generated_words.add(word)

    # 过滤：移除存在对应原生小写版本的大写单词
    filtered_blanks = {word for word in blank_generated_words if word.lower() not in native_words}

    # 合并最终结果
    return list(native_words.union(filtered_blanks))

# 测试案例
start = time.perf_counter()
result = find_all_word_combinations('abcde__')
print(f"生成单词总数：{len(result)}")
end = time.perf_counter()
print(f'耗时：{end - start:.2f} 秒')

优化效果说明 #

• 性能提升：原代码在5字母+2空白场景下耗时超1分钟，重构后可压缩至数秒内完成（具体耗时取决于硬件）
• 功能修正：正确区分原生小写与空白生成的大写单词，准确实现“移除有对应小写版本的大写单词”的需求
• 内存优化：用集合去重减少冗余数据，降低内存占用

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