在Python中找到从一个单词到另一个单词的最短路径

Question

想象一下您想要找到两个长度相同的单词之间的最短路径之一。
每一步都是性格的改变。
新单词必须在使用的dictionary.txt文件中。

从 LANE 到 BODY 的示例可以是：
LANE
LONE
BONE
BONY
BODY

我编写了一个简单的Python代码来完成这个任务。

对于 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}")

PS：我要解决的游戏通常称为Laddergram。

Answer 1

Levenshtein 包是你的朋友

import Levenshtein

start_word = 'LANE'
end_word = 'BODY'

edit_list = Levenshtein.editops('LANE', 'BODY')
temp = start_word
print(temp)
for idx in range(len(edit_list)):
    temp = Levenshtein.apply_edit(edit_list[idx:idx+1], temp, 'BODY')
    print(temp)

LANE
BANE
BONE
BODE
BODY