如何优化Python代码，从字典文件中高效匹配指定字母组的单词对？

需求：从dictionary.txt文件中，找出由给定无重复字母字符串（如GRIHWSNYP）的所有字母组成的单词对，要求两个单词的字母完全覆盖该字符串且无重叠。

字典文件示例：

AARHUS
AARON
ABABA
ABACK
...

预期输出示例：

>>> f('GRIHWSNYP')
The pairs of words using all (distinct) letters in "GRIHWSNYP" are:
('SPRING', 'WHY')
...

原代码的核心效率问题 #

原代码可运行但性能极差，主要问题集中在：

• 双重循环遍历全字典，时间复杂度为O(n²)，字典规模较大时（如十万级单词）会直接导致运行超时
• 每次添加结果后都执行sorted(set(solutions))，反复的集合转换和排序操作带来大量不必要的开销
• 未对字典做预处理，查找补集对应的单词时需要遍历全字典，无针对性优化

优化思路与实现 #

优化方向 #

1. 预处理字典，构建快速查找映射：过滤含重复字母的单词后，将相同字母集合的单词分组存储，后续查找直接查表，无需遍历全字典
2. 减少无效遍历：只处理字母集合是目标字符串子集的单词，跳过无关项
3. 高效去重：用集合存储结果对（排序后存入），最后统一排序输出，避免反复排序去重

优化后的代码 #

def find_word_pairs(letters):
    dictionary_path = 'dictionary.txt'
    target_letters = frozenset(letters.upper())
    target_total_len = len(target_letters)
    
    # 预处理字典：构建「字母集合-对应单词列表」的映射
    letter_set_to_words = {}
    with open(dictionary_path, 'r') as f:
        for line in f:
            word = line.strip().upper()
            # 过滤含重复字母的单词
            if len(word) != len(set(word)):
                continue
            word_letters = frozenset(word)
            # 将单词加入对应字母集合的列表
            if word_letters not in letter_set_to_words:
                letter_set_to_words[word_letters] = []
            letter_set_to_words[word_letters].append(word)
    
    solutions = set()
    # 遍历所有符合条件的单词集合
    for word_set, words in letter_set_to_words.items():
        # 跳过字母集合不是目标子集的情况
        if not word_set.issubset(target_letters):
            continue
        # 计算补集字母集合
        complement_set = target_letters - word_set
        # 补集为空则跳过（单个单词覆盖所有字母，不符合单词对要求）
        if not complement_set:
            continue
        # 查找补集对应的单词列表
        if complement_set in letter_set_to_words:
            complement_words = letter_set_to_words[complement_set]
            # 生成不重复的单词对（排序后存入集合避免(A,B)和(B,A)重复）
            for word1 in words:
                for word2 in complement_words:
                    sorted_pair = tuple(sorted((word1, word2)))
                    solutions.add(sorted_pair)
    
    # 输出结果
    if not solutions:
        print('There is no solution.')
    else:
        print(f'The pairs of words using all (distinct) letters in "{letters}" are:')
        for pair in sorted(solutions):
            print(pair)

进阶优化：位掩码加速（针对超大规模字典） #

如果字典规模极大（如百万级单词），可以用位掩码替代冻结集合，进一步提升运算和查找速度：

• 每个字母对应一个二进制位（如A对应第0位，B对应第1位）
• 用整数表示单词的字母集合（位运算快速计算补集、子集关系）

示例位掩码版预处理代码：

def word_to_mask(word):
    mask = 0
    for c in word.upper():
        if not c.isalpha():
            continue
        bit_pos = ord(c) - ord('A')
        mask |= 1 << bit_pos
    return mask

# 预处理构建「掩码-对应单词列表」的映射
mask_to_words = {}
with open(dictionary_path, 'r') as f:
    for line in f:
        word = line.strip().upper()
        if len(word) != len(set(word)):
            continue
        word_mask = word_to_mask(word)
        if word_mask not in mask_to_words:
            mask_to_words[word_mask] = []
        mask_to_words[word_mask].append(word)

后续查找逻辑可替换为位运算：

target_mask = word_to_mask(letters)
for word_mask, words in mask_to_words.items():
    # 位运算判断是否是目标子集
    if (word_mask & target_mask) != word_mask:
        continue
    # 位运算计算补集掩码
    complement_mask = target_mask & (~word_mask)
    if complement_mask == 0:
        continue
    if complement_mask in mask_to_words:
        complement_words = mask_to_words[complement_mask]
        # 生成单词对逻辑同前

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