Word Ladder II

Word Ladder II is the boss level of the BFS family. It is not enough to find a shortest transformation sequence — you must find every one. The trick is to run BFS for distance and record parent links along the way, then backtrack them.

The slow way first

You might try a plain DFS that explores every path and keeps the shortest ones. But the number of paths explodes, and you cannot tell a path is too long until you have walked the whole thing. That is exponential work for no good reason.

The question to ask: what is the shortest distance to each word, and which words could come right before it on a shortest path? BFS answers the first part for free — it visits words in order of distance. If we also remember, for each word, the set of words that first reached it, we have everything we need.

The idea: BFS for distance, parents for the paths

Process the graph one level at a time. Each level is the set of words at the same distance from begin. When a word in the current level reaches a new word, record that current word as a parent of the new one. A word can have several parents if two words on the same level both reach it — that is how multiple ladders arise. Stop as soon as end appears. Then DFS-backtrack the parent links from end back to begin to rebuild every shortest ladder.

The key insight: only record a parent when a word is discovered on the current level. That keeps every recorded link on a shortest path, so backtracking can never produce a too-long ladder.

Walk through it

Step through the animation. BFS fans out from hit: level 1 is hot, level 2 is dot and lot, level 3 is dog and log. On level 4 both dog and log reach cog, so cog ends up with two parents. Backtracking from cog follows each parent chain back to hit, producing both shortest ladders.

Pseudocode

words = set(wordList)
layer = {begin}                      # current BFS frontier
parents = empty map word -> set of parents
while layer is non-empty and end not yet found:
    next_layer = empty map
    for each word in layer:
        for each one-letter neighbor nxt in words:
            if nxt has no parents yet:
                add word to next_layer[nxt]
    merge next_layer into parents
    layer = the keys of next_layer
backtrack from end through parents, collecting reversed paths
return all collected ladders

The Python solution

def find_ladders(begin, end, words):
    words = set(words)
    layer = {begin}
    parents = defaultdict(set)
    while layer and end not in parents:
        next_layer = defaultdict(set)
        for word in layer:
            for nxt in one_letter_neighbors(word, words):
                if nxt not in parents:
                    next_layer[nxt].add(word)
        parents.update(next_layer)
        layer = set(next_layer)
    res, path = [], [end]
    def backtrack(word):
        if word == begin:
            res.append(path[::-1])
        else:
            for p in parents[word]:
                path.append(p); backtrack(p); path.pop()
    backtrack(end)
    return res

• layer is the current BFS frontier — the set of words at the same distance from begin.
• parents[nxt] holds every word that first reached nxt. A set, because there can be more than one.
• The check if nxt not in parents guards that we only record links to words discovered for the first time, i.e. on a shortest path.
• We loop while layer and end not in parents, so BFS stops the moment end is reached — no longer ladder can slip in.
• backtrack walks the parent links from end to begin, reversing each completed chain into a ladder.

Complexity

N is the number of words and L is the word length. Building neighbors costs O(L · 26) per word, and the parent map plus the answer ladders dominate the space. The backtracking only walks edges on shortest paths, so it adds nothing asymptotically beyond the output size.

When this pattern shows up

Practice