求优化单词阶梯（Laddergram）最短路径查找Python代码

需求与问题 #

实现同长度单词间的最短字符替换路径（对应Laddergram游戏）：每步仅替换一个字符，且生成的新单词必须存在于dictionary.txt字典文件中。例如从LANE到BODY的路径为：LANE→LONE→BONE→BONY→BODY。

当前代码处理6个及以上字符的单词时速度较慢，且无法确认是否找到最短路径，现对代码进行审查与优化。

原代码 #

from collections import deque
import time


def load_words(word_length):
    with open('dictionary.txt', encoding="utf8") as file:
        words = {line.strip() for line in file if len(line.strip()) == word_length}
    return words


def get_neighbors(word, word_set):
    neighbors = []
    for i in range(len(word)):
        for char in 'abcdefghijklmnopqrstuvwxyz':
            if char != word[i]:
                new_word = word[:i] + char + word[i + 1:]
                if new_word in word_set:
                    neighbors.append(new_word)
    return neighbors


def find_shortest_path(start, end):
    if start == end:
        return [start]

    word_set = load_words(len(start))

    if start not in word_set or end not in word_set:
        return None

    queue = deque([(start, [start])])
    visited = {start}

    while queue:
        current_word, path = queue.popleft()

        for neighbor in get_neighbors(current_word, word_set):
            if neighbor == end:
                return path + [neighbor]
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return None


start_word = input("Insert the starting word: ")
end_word = input("Insert the ending word: ")
start_time = time.time()
if not start_word.isalpha():
    print(f"Invalid input: {start_word} contains not alphabetic characters.")
elif not end_word.isalpha():
    print(f"Invalid input: {end_word} contains not alphabetic characters.")
elif len(start_word) != len(end_word):
    print(f"Invalid input: {start_word} and {end_word} must be the same length")
else:
    start_word = start_word.lower()
    end_word = end_word.lower()
    path_found = find_shortest_path(start_word, end_word)
    if path_found:
        print(f"\nMinimum path length is: {len(path_found) - 1}")
        print("\n".join(path_found).upper())
    else:
        print(f"\nDoesnt' exist any path from {start_word} to {end_word}.")
print(f"Time taken: {time.time() - start_time}")

关键说明与优化点 #

1. 最短路径的确认 #

原代码采用广度优先搜索（BFS），BFS的特性是优先遍历所有距离起点最近的节点，因此第一次找到终点时的路径必然是最短路径，无需额外验证。

2. 速度优化方案 #

（1）预生成模式映射替代逐字符枚举

原get_neighbors函数通过逐个替换字符生成新单词再查字典，效率极低。改为预先生成"模式-单词"映射：将每个单词的每个位置替换为通配符（如*），把相同模式的单词归为一组。例如单词lane会生成*ane、l*ne、la*e、lan*四个模式，每个模式对应所有符合该结构的单词。

找邻居时，只需生成当前单词的所有模式，直接取对应模式下的单词即可，无需逐字符枚举。

（2）双向BFS减少搜索空间

单向BFS的搜索空间会随着步数指数增长，双向BFS同时从起点和终点开始搜索，当两边的搜索集合出现交集时，即可拼接出最短路径，能大幅减少搜索节点数量，尤其是长单词场景下效率提升显著。

（3）缓存字典加载结果

原代码每次调用find_shortest_path都会重新加载字典，改为缓存不同长度的单词集合和模式映射，避免重复IO操作。

（4）记录父节点替代路径复制

原代码每次入队都会复制整个路径列表，内存开销大。改为记录每个节点的父节点，找到交集后再回溯生成路径，节省内存和时间。

优化后的代码 #

from collections import deque, defaultdict
import time

# 缓存不同长度的单词集合和模式映射
word_cache = {}
pattern_map_cache = {}


def load_words_and_patterns(word_length):
    if word_length in word_cache and word_length in pattern_map_cache:
        return word_cache[word_length], pattern_map_cache[word_length]
    
    word_set = set()
    pattern_map = defaultdict(list)
    
    with open('dictionary.txt', encoding="utf8") as file:
        for line in file:
            word = line.strip().lower()
            if len(word) == word_length:
                word_set.add(word)
                # 生成当前单词的所有模式
                for i in range(word_length):
                    pattern = word[:i] + '*' + word[i+1:]
                    pattern_map[pattern].append(word)
    
    word_cache[word_length] = word_set
    pattern_map_cache[word_length] = pattern_map
    return word_set, pattern_map


def get_neighbors(word, pattern_map):
    neighbors = set()
    word_len = len(word)
    for i in range(word_len):
        pattern = word[:i] + '*' + word[i+1:]
        # 取当前模式下的所有单词，排除自身
        for neighbor in pattern_map[pattern]:
            if neighbor != word:
                neighbors.add(neighbor)
    return neighbors


def find_shortest_path(start, end):
    if start == end:
        return [start]
    
    word_len = len(start)
    word_set, pattern_map = load_words_and_patterns(word_len)
    
    if start not in word_set or end not in word_set:
        return None
    
    # 双向BFS的两个队列和父节点记录
    start_queue = deque([start])
    end_queue = deque([end])
    
    start_visited = {start: None}
    end_visited = {end: None}
    
    while start_queue and end_queue:
        # 处理起点方向的一层节点
        current_level_size = len(start_queue)
        for _ in range(current_level_size):
            current_word = start_queue.popleft()
            # 检查是否和终点方向的访问集合有交集
            if current_word in end_visited:
                # 拼接路径：起点到交集节点 + 终点到交集节点的反向
                path = []
                temp = current_word
                while temp:
                    path.append(temp)
                    temp = start_visited[temp]
                path.reverse()
                temp = end_visited[current_word]
                while temp:
                    path.append(temp)
                    temp = end_visited[temp]
                return path
            
            for neighbor in get_neighbors(current_word, pattern_map):
                if neighbor not in start_visited:
                    start_visited[neighbor] = current_word
                    start_queue.append(neighbor)
        
        # 处理终点方向的一层节点
        current_level_size = len(end_queue)
        for _ in range(current_level_size):
            current_word = end_queue.popleft()
            if current_word in start_visited:
                path = []
                temp = start_visited[current_word]
                while temp:
                    path.append(temp)
                    temp = start_visited[temp]
                path.reverse()
                path.append(current_word)
                temp = end_visited[current_word]
                while temp:
                    path.append(temp)
                    temp = end_visited[temp]
                return path
            
            for neighbor in get_neighbors(current_word, pattern_map):
                if neighbor not in end_visited:
                    end_visited[neighbor] = current_word
                    end_queue.append(neighbor)
    
    return None


start_word = input("输入起始单词：")
end_word = input("输入目标单词：")
start_time = time.time()

if not start_word.isalpha():
    print(f"无效输入：{start_word}包含非字母字符。")
elif not end_word.isalpha():
    print(f"无效输入：{end_word}包含非字母字符。")
elif len(start_word) != len(end_word):
    print(f"无效输入：{start_word}和{end_word}长度必须相同")
else:
    start_word = start_word.lower()
    end_word = end_word.lower()
    path_found = find_shortest_path(start_word, end_word)
    if path_found:
        print(f"\n最短路径长度：{len(path_found) - 1}")
        print(" → ".join(path_found).upper())
    else:
        print(f"\n不存在从{start_word}到{end_word}的路径。")

print(f"耗时：{time.time() - start_time:.4f}秒")

优化效果说明 #

• 预生成模式映射将邻居查找的时间复杂度从O(26*N)降至O(M)（M为同模式单词数量），长单词场景下效率提升明显。
• 双向BFS将搜索空间从O(b^d)降至O(b(d/2))（b为平均分支数，d为最短路径长度），大幅减少遍历节点数。
• 缓存机制避免了重复加载字典的IO开销。
• 父节点记录减少了路径复制的内存和时间开销。

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