Word Ladder

LeetCode 127 · View on LeetCode

BFS from beginWord. At each step, try changing every character to a-z. If the new word is in the word list, add it to the queue. BFS guarantees the shortest transformation sequence.

from collections import deque

def ladder_length(begin_word: str, end_word: str, word_list: list[str]) -> int:
    word_set = set(word_list)
    if end_word not in word_set:
        return 0
    queue = deque([(begin_word, 1)])
    visited = {begin_word}
    while queue:
        word, steps = queue.popleft()
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = word[:i] + c + word[i+1:]
                if next_word == end_word:
                    return steps + 1
                if next_word in word_set and next_word not in visited:
                    visited.add(next_word)
                    queue.append((next_word, steps + 1))
    return 0

if __name__ == '__main__':
    print(ladder_length("hit", "cog", ["hot","dot","dog","lot","log","cog"]))  # 5
    print(ladder_length("hit", "cog", ["hot","dot","dog","lot","log"]))        # 0