Word Ladder

Intuition

Think of each word as a node, with an edge connecting two words that differ in exactly one letter. The shortest transformation sequence is then the shortest path in this graph, which breadth-first search computes level by level. Instead of comparing every pair of words, we generate each one-letter variant of the current word and check membership in a hash set built from the word list, which is far faster. Every time we reach a new word we remove it from the set, ensuring each word is processed only once. The level count, starting at 1 for beginWord, equals the number of words on the path when we first meet endWord.

Algorithm walkthrough

1. 1Put the word list into a hash set for O(1) lookups; if endWord is absent, return 0 because the target is unreachable.
2. 2Seed a queue with beginWord and set the current level to 1, where the level counts the words in the sequence so far.
3. 3Process the queue one full level at a time; if any dequeued word equals endWord, return the current level.
4. 4For each word, replace each position with every letter from a to z to form candidate words.
5. 5Whenever a candidate exists in the set, remove it and enqueue it for the next level so it is never revisited.
6. 6After a level finishes, increment the level; if the queue drains without reaching endWord, return 0.

Implementation

from collections import deque

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:
        word_set = set(wordList)
        if endWord not in word_set:
            return 0
        queue = deque([beginWord])
        level = 1
        while queue:
            for _ in range(len(queue)):
                word = queue.popleft()
                if word == endWord:
                    return level
                for i in range(len(word)):
                    for c in "abcdefghijklmnopqrstuvwxyz":
                        candidate = word[:i] + c + word[i + 1:]
                        if candidate in word_set:
                            word_set.remove(candidate)
                            queue.append(candidate)
            level += 1
        return 0