Word Ladder

Word Ladder turns a word puzzle into a graph problem. Once you see words as nodes and one-letter changes as edges, the answer is just a shortest path — and the tool for shortest path on an unweighted graph is breadth-first search (BFS).

The slow way first

You could try to explore greedily — keep changing letters and hope you stumble onto cog. But which neighbor do you pick first? A wrong guess sends you down a long detour, and depth-first search can find a path that is far from the shortest. We do not just want any ladder; we want the shortest one.

The question to ask: how do I guarantee the first solution I find is the shortest? Explore the graph in layers — all words one step away, then all words two steps away, and so on. The first time a layer contains cog, that layer number is the answer.

The idea: BFS over a word graph

Picture each word as a node. Draw an edge between two words when they differ by exactly one letter. Now run BFS from begin: process words in waves, tracking each word's distance (its position in the ladder). Because BFS finishes an entire layer before touching the next, the first time we reach end we have reached it by the shortest route.

We never build the whole edge list up front; for each popped word we generate its one-letter neighbors and keep only the ones in the word set. A seen set stops us from revisiting a word.

Walk through it

Step through the animation. Layer 1 is just hit. Its only neighbor is hot (layer 2). From hot we reach dot and lot (layer 3); from those, dog and log (layer 4). Finally dog connects to cog, so cog lands in layer 5 — and since BFS got there first, 5 is the shortest ladder length.

Pseudocode

put (begin, 1) in a queue           # distance counts words, start = 1
mark begin as seen
while the queue is not empty:
    word, dist = pop the front
    for each word one letter away that is in the list:
        if it equals end:
            return dist + 1          # first time we reach end = shortest
        if not seen:
            mark it seen
            push (neighbor, dist + 1)
return 0                             # end unreachable

The Python solution

def ladder_length(begin, end, word_list):
    words = set(word_list)
    queue = deque([(begin, 1)])
    seen = {begin}
    while queue:
        word, dist = queue.popleft()
        for nxt in one_letter_neighbors(word, words):
            if nxt == end:
                return dist + 1
            if nxt not in seen:
                seen.add(nxt)
                queue.append((nxt, dist + 1))
    return 0

• words is a set so the membership check for each candidate neighbor is O(1).
• queue holds (word, distance) pairs; distance is how many words deep this word sits in the ladder.
• seen prevents re-enqueuing a word, which is what keeps BFS from looping forever.
• popleft() takes from the front — that FIFO order is exactly what makes the search proceed layer by layer.
• Lines 8-9 are the heart: the first time a neighbor equals end, BFS has reached it on the shortest path, so we return immediately.

Complexity

Here N is the number of words and L the word length. Each word is dequeued once; generating its neighbors costs O(L * 26). The seen set and queue hold up to N words.

When this pattern shows up

Practice