• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000, and every word has the same length
• All words consist of lowercase English letters
• beginWord != endWord, and all words in wordList are distinct

Nothing in this statement mentions a graph, a grid, or a distance. It talks about words and letters. So the first real task is not to pick an algorithm but to notice that the problem is a shortest-path problem in disguise, and that recognition is the skill worth extracting.

A graph is nothing more than a set of things plus a rule about which pairs are directly connected. Apply that definition literally here.

With that in place, "shortest transformation sequence" reads as "shortest path from beginWord to endWord", and the equal-cost property is exactly the condition under which the simplest shortest-path method works.

The unusual part, compared to a grid problem, is that nobody hands you the edges. In a grid the neighbours of a cell are obvious from its coordinates. Here they must be computed, and how you compute them turns out to dominate the running time. This is what people mean by a state space problem: the graph is implied by a rule, it is generated as you walk it, and it is never built or stored in full.

The search strategy follows from the equal-cost property. Consider all words one step from beginWord — call that layer 1. Layer 2 is every unused word one step from layer 1, and so on. A word first appears in the layer matching its true minimum distance: it cannot appear earlier, since that would mean a shorter chain exists, and it cannot appear later, because as soon as any layer-d word is expanded, all of its unused neighbours are claimed for layer d+1.

So the first time endWord appears, the count is final. There is no need to compare competing sequences and no best-so-far to maintain — discovery order is distance order. Expanding layer by layer like this is Breadth-First Search, and it needs a queue, which hands words back in the order they were found. Using a stack instead would drive the search deep down one chain before finishing the current layer, and the first arrival at endWord would no longer be the shortest.

The direct approach is to compare the current word against every word in the list and keep the ones differing in a single position.

def neighbours(word, word_list):
    result = []
    for candidate in word_list:
        diff = sum(1 for a, b in zip(word, candidate) if a != b)
        if diff == 1:
            result.append(candidate)
    return result

Count the cost. Each comparison examines L letters, there are N words to compare against, and this runs once per word expanded, so the search totals O(N² × L). With N at 5000 and L at 10, that is around 250 million letter comparisons — slow, and it scales badly in exactly the dimension the constraints allow to grow.

The waste is specific: the vast majority of those comparisons find words differing in five or six positions, which were never plausible neighbours. We are scanning a whole dictionary to find items that a rule could have described directly.

Turn it around. Rather than asking which existing words are one letter away, construct every string that is one letter away and test which of them are real words. For a word of length L there are exactly L × 25 such strings, and testing membership in a set — a structure that answers "is this present?" by hashing the value to a slot rather than scanning — costs constant time.

from collections import deque

def ladder_length(begin_word, end_word, word_list):
    words = set(word_list)
    if end_word not in words:
        return 0

    queue = deque([(begin_word, 1)])        # the sequence so far contains 1 word
    words.discard(begin_word)

    while queue:
        word, length = queue.popleft()
        if word == end_word:
            return length

        for i in range(len(word)):
            for ch in "abcdefghijklmnopqrstuvwxyz":
                candidate = word[:i] + ch + word[i + 1:]
                if candidate in words:
                    words.remove(candidate)          # claim it: never queue it twice
                    queue.append((candidate, length + 1))
    return 0

The cost per word expanded is L positions × 26 letters × O(L) to build each candidate string, so O(L² × 26), and with N words in total the search is O(N × L² × 26). For the given limits that is a few million operations instead of hundreds of millions.

Dictionary {hot, dot, dog, lot, log, cog}. Distances are counts of words in the sequence, so beginWord starts at 1.

The sequence found is hit, hot, dot, dog, cog. The path through lot and log is equally short, and the algorithm simply reports the same count without caring which one it traced.

Now the second example, with cog absent from the list. The guard at the top fires immediately and returns 0 without any search. Without that guard the algorithm would still return 0, but only after exhausting the entire reachable component — correct but wasteful, and interviewers notice the check.

There is one more gear, and it is the standard follow-up. BFS from a single origin expands a ball of radius d. If each word has roughly b neighbours, that ball holds on the order of b^d words, which grows brutally with distance.

Now run two searches at once — one forward from beginWord, one backward from endWord — and expand whichever frontier is currently smaller. They meet in the middle, so each has only travelled about d/2 layers, giving roughly 2 × b^(d/2) words examined instead of b^d. For b = 10 and d = 6 that is a few thousand instead of a million.

The bookkeeping is simple: keep two sets of frontier words, and at each round expand the smaller one and test whether any generated word appears in the opposite frontier. When one does, the two half-lengths sum to the answer. Bidirectional search is valid here for a specific reason worth stating — the "differs by one letter" relation is symmetric, so a step is traversable in both directions. On a directed graph with one-way edges you would need the reverse adjacency to search backwards at all.

The grid problems in this section hand you the graph. This one does not, and that is the whole lesson. When a statement describes configurations and legal moves between them — words and letter swaps, a lock and wheel turns, a board and piece slides, a number and arithmetic operations — run the same three questions:

Then add the two guards that make it work: a set for constant-time membership, and claiming states at discovery rather than at expansion.

Train the reflex: the phrase minimum number of moves to turn X into Y is a shortest-path problem no matter what X and Y are made of. Your job is to name the nodes.