如何从已排序字符串顶点列表高效生成边（不修改数据结构）

问题背景 #

给定已排序的字符串顶点列表，要求不修改现有数据结构，寻找比两层嵌套循环更高效的边生成方式。当前使用的两层循环代码如下：

for word in vertices:
    for other_word in vertices:
        # 检查顶点是否连通并添加边
        weight = get_weight(word, other_word)
        if weight != -1:
            # 添加边

曾尝试跳过重复顶点对的优化，但面对大规模数据时性能依旧很差：

for word in vertices:
    for other_word in vertices:
        if other_word <= word:
            continue
        else:
            # 检查顶点是否连通并添加边

补充说明：判断顶点连通性的get_weight函数逻辑如下（本次重点不在优化该函数本身）：

def get_weight(word1, word2):
    weight = -1
    if isAnagram(word1, word2):
        weight = 1
    elif one_letter_diff(word1, word2):
        weight = 2
    # 其他判断逻辑
    return weight

最终目标是通过Dijkstra算法计算指定两单词间的最短路径。

优化方案 #

1. 变位词分组预处理，减少重复判断 #

变位词的核心特征是字符组成完全一致，先遍历一次顶点列表，将所有变位词归类到同一组：

from collections import defaultdict

anagram_groups = defaultdict(list)
for word in vertices:
    # 以排序后的字符串作为键，确保变位词的键完全相同
    key = ''.join(sorted(word))
    anagram_groups[key].append(word)

同一组内的所有单词两两之间权重为1，直接生成组内的边即可，无需再调用isAnagram做重复判断，能大幅减少无效计算。

2. 掩码模式匹配，快速定位单字母差异单词 #

针对单字母差异的场景，可通过生成“模糊掩码模式”构建映射表：

pattern_map = defaultdict(list)
# 假设所有单词长度一致，若长度不同可先按长度分组再处理
word_length = len(vertices[0])

for word in vertices:
    for i in range(word_length):
        # 将单词的每个位置替换为通配符*，生成对应的模式
        pattern = word[:i] + '*' + word[i+1:]
        pattern_map[pattern].append(word)

处理每个单词时，遍历其所有掩码模式，从pattern_map中取出对应的单词列表，这些单词就是与当前单词单字母差异的候选，直接生成权重为2的边即可，避免了与所有单词逐一比对。

3. 结合有序列表特性，用二分查找加速匹配 #

利用顶点列表已排序的特点，对单字母差异的候选单词进行二分查找，快速验证是否存在于列表中：

import bisect

alphabet = 'abcdefghijklmnopqrstuvwxyz'
word_length = len(vertices[0])

for word in vertices:
    for i in range(word_length):
        original_char = word[i]
        for c in alphabet:
            if c == original_char:
                continue
            # 生成单字母替换后的候选单词
            candidate = word[:i] + c + word[i+1:]
            # 二分查找判断候选是否存在于顶点列表
            idx = bisect.bisect_left(vertices, candidate)
            if idx < len(vertices) and vertices[idx] == candidate:
                # 生成权重为2的边
                pass

这种方式跳过了大量不可能匹配的单词，比全量遍历效率提升显著。

4. 延迟加载边，按需生成 #

既然最终要执行Dijkstra算法，无需提前生成所有边。可在Dijkstra遍历过程中，处理当前单词时再通过上述方法找出所有连通单词，作为邻接节点加入优先级队列。这种方式既节省内存，又避免了预处理所有边的时间开销，在顶点数量极大的场景下优势尤为明显。

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