如何优化单字母差异单词查找的Python代码以提升运行效率？

我需要从单词列表中找出所有仅存在单字母差异的单词组并输出为数组，当前处理18000个单词耗时17秒，希望缩短运行时间。原代码如下：

# 比较两个单词是否仅单字母差异
def isneighbour(word1, word2):
    diff = 0
    for i in range(len(word1)):
        if word1[i] != word2[i]:
            diff += 1
            if diff > 1:
                return False
    return diff == 1


def find_neighbours(lst):
    hood = []
    keylst = list(lst.keys())
    length = len(keylst) -1
    for i in range(0, length -1):
        temp = []
        temp.append(keylst[i])
        for j in range(i + 1, length):
            if len(keylst[i]) == len(keylst[j]):
                if isneighbour(keylst[i], keylst[j]):
                    temp.append(keylst[j])
        if len(temp)>1:
            quicksort(temp)
            hood.append(temp)
    return hood

核心优化思路：从O(n²)降到O(k*m)（k为单词总数，m为单词平均长度） #

原代码的嵌套循环是典型的O(n²)复杂度，当n=18000时，无效比较量会急剧膨胀。以下是具体优化方案：

1. 按单词长度预分组，砍掉无效比较 #

不同长度的单词不可能存在单字母差异，先把所有单词按长度归类，只在同长度的单词组内处理，直接避免跨长度的无效判断。

2. 用「模式映射法」快速定位邻居单词 #

对于每个单词，生成所有单字母占位符模式：比如单词cat，生成_at、c_t、ca_（用占位符替换每个位置的字母）。所有共享同一模式的单词，互相之间必然是单字母差异（仅在占位符位置不同）。用字典存储模式到单词列表的映射，就能一次性找出所有邻居组。

优化后的代码示例 #

from collections import defaultdict

def find_neighbours_optimized(word_dict):
    # 按单词长度分组
    words_by_length = defaultdict(list)
    for word in word_dict.keys():
        words_by_length[len(word)].append(word)
    
    hood = []
    seen_groups = set()  # 避免重复添加相同的组
    
    for word_list in words_by_length.values():
        # 构建模式到单词列表的映射
        pattern_map = defaultdict(list)
        for word in word_list:
            for i in range(len(word)):
                # 生成单字母占位符模式
                pattern = word[:i] + '_' + word[i+1:]
                pattern_map[pattern].append(word)
        
        # 提取有效组并去重
        for group in pattern_map.values():
            if len(group) >= 2:
                sorted_group = tuple(sorted(group))  # 转成可哈希元组用于去重
                if sorted_group not in seen_groups:
                    seen_groups.add(sorted_group)
                    hood.append(list(sorted_group))
    
    return hood

3. 细节优化补充 #

• 替换手写quicksort：Python内置的sorted()函数经过C级优化，性能远高于手写排序逻辑。
• 避免重复遍历：原代码中每个单词会和后续所有单词逐一比较，而模式映射法仅需为每个单词生成m个模式（m为单词长度），计算量大幅降低。

性能对比 #

原代码处理18000个单词时，嵌套循环会执行约1.6亿次比较；优化后的代码执行次数约为18000 * 平均单词长度（比如平均长度5的话仅9万次操作），耗时可从17秒压缩到毫秒级。

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