Word Ladder II — All Shortest Transformation Paths via BFS plus DFS

Problem Statement#

Given two words beginWord and endWord, plus a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord. Each transformation must change exactly one letter, every intermediate word must be present in the dictionary, and beginWord does not need to be in wordList. If no such transformation exists, return an empty list. Each output sequence is a list of words ordered from beginWord to endWord.

This is a multi-source shortest-path enumeration problem on an implicit graph where each word is a node and an edge connects words that differ by exactly one letter.

Why This Problem Matters#

Word Ladder II is one of the hardest BFS problems on LeetCode and a stress test favorite at Amazon, Google, and Facebook interviews. It rewards candidates who have moved beyond pattern matching and actually understand what BFS guarantees. A naive DFS or backtracking approach times out instantly because the branching factor is the alphabet size times the word length and there are exponentially many non-shortest paths. The trick is to combine BFS for the shortest-distance discovery with a backward DFS for path reconstruction.

This problem is also a tutorial in graph reduction. The implicit graph has up to 5,000 words and 25 letter swaps per position; building the explicit edge list costs more than running the BFS. Strong candidates know how to defer edge generation, batch it per layer, and prune visited nodes only after the entire layer is processed so that all parent links survive.

The Core Insight#

To enumerate all shortest paths, you need two pieces of information: the shortest distance from beginWord to every reachable word and a record of every predecessor that contributed to a shortest path. A standard BFS gives you the distance; the trick is to also maintain a parents map where parents[word] is the set of words from which word was first reached at its shortest distance. Once BFS finishes, a DFS that walks backward from endWord through the parents map reconstructs every shortest path in linear output time.

The BFS must process the graph layer by layer rather than node by node so that all parents at the same shortest distance get recorded before any of them gets removed from the dictionary. If you remove a word from the dictionary the moment you visit it, you lose the ability to record alternate shortest-path predecessors discovered later in the same layer. The clean fix is to subtract the entire current layer from the dictionary only after computing the next layer.

Visual Dry Run (BFS/DFS trace)#

Take beginWord equal to hit, endWord equal to cog, and wordList equal to [hot, dot, dog, lot, log, cog].

Layer 0. layer equals the set containing hit. parents is empty. words still contains all six dictionary entries.

Layer 1. We remove hit from the dictionary candidates. From hit we generate neighbors that are exactly one letter off: hot is in words. Add hot to nxt, set parents[hot] to the set containing hit. Move to layer 1 equal to the set containing hot.

Layer 2. We remove hot from words. From hot we generate dot and lot, both in the dictionary. Add both to nxt, set parents[dot] to set with hot, set parents[lot] to set with hot. Move to layer 2.

Layer 3. We remove dot and lot from words. From dot we generate dog (in words) and lot (already removed). From lot we generate log (in words) and dot (already removed). Add dog and log. parents[dog] is the set with dot. parents[log] is the set with lot. Move to layer 3.

Layer 4. We remove dog and log. From dog we generate cog and log (already removed). From log we generate cog and dog (already removed). Add cog to nxt. parents[cog] is the set with dog and log. Mark found true.

DFS from cog walks backward. Visit cog, predecessors are dog and log. Branch one: cog, dog, dot, hot, hit, reverse to get [hit, hot, dot, dog, cog]. Branch two: cog, log, lot, hot, hit, reverse to get [hit, hot, lot, log, cog]. The function returns both lists.

Solution (Optimal)#

Python#

from collections import deque, defaultdict
 
class Solution:
    def findLadders(self, beginWord, endWord, wordList):
        words = set(wordList)
        if endWord not in words:
            return []
        parents = defaultdict(set)
        layer = {beginWord}
        found = False
 
        while layer and not found:
            words -= layer
            nxt = set()
            for word in layer:
                for i in range(len(word)):
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        nw = word[:i] + c + word[i+1:]
                        if nw in words:
                            nxt.add(nw)
                            parents[nw].add(word)
                            if nw == endWord:
                                found = True
            layer = nxt
 
        if not found:
            return []
 
        res = []
        def dfs(word, path):
            if word == beginWord:
                res.append([beginWord] + list(reversed(path)))
                return
            for p in parents[word]:
                path.append(p)
                dfs(p, path)
                path.pop()
 
        dfs(endWord, [endWord])
        return res

JavaScript#

var findLadders = function(beginWord, endWord, wordList) {
    const words = new Set(wordList);
    if (!words.has(endWord)) return [];
    const parents = new Map();
    let layer = new Set([beginWord]);
    let found = false;
 
    while (layer.size && !found) {
        for (const w of layer) words.delete(w);
        const next = new Set();
        for (const word of layer) {
            for (let i = 0; i < word.length; i++) {
                for (let c = 97; c < 123; c++) {
                    const nw = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
                    if (words.has(nw)) {
                        next.add(nw);
                        if (!parents.has(nw)) parents.set(nw, new Set());
                        parents.get(nw).add(word);
                        if (nw === endWord) found = true;
                    }
                }
            }
        }
        layer = next;
    }
 
    const res = [];
    if (!found) return res;
    const dfs = (word, path) => {
        if (word === beginWord) {
            res.push([beginWord, ...path.slice().reverse()]);
            return;
        }
        for (const p of parents.get(word) || []) {
            path.push(p);
            dfs(p, path);
            path.pop();
        }
    };
    dfs(endWord, [endWord]);
    return res;
};

Time complexity is O(N times L squared times 26) for BFS where N is the dictionary size and L is the word length, plus O(P) for path reconstruction where P is the total length of all answers. Space complexity is O(N times L) for the parents map and visited tracking.

Common Mistakes#

Removing words from the dictionary the moment you visit them inside the inner loop. This erases parent links for siblings still being processed in the same layer and silently drops valid shortest paths. The fix is to subtract the entire layer in bulk before generating neighbors. Running an unbounded DFS instead of layered BFS yields exponential blowup. Forgetting that beginWord may not be in the dictionary leads to incorrect failure. Storing parents as a list rather than a set allows duplicate entries and inflates the answer count when the same parent reaches a word through multiple letter swaps in the same layer (rare but possible with palindromes). Building the full neighbor graph up front instead of generating neighbors lazily during BFS uses too much memory on large dictionaries.

Interview Tips#

Lead with the structural observation: shortest path means BFS, all paths means parent tracking, output reconstruction means DFS. Discuss the layer-bulk-removal subtlety because interviewers love when candidates anticipate the parent-loss bug. State the time complexity in terms of N, L, and the alphabet size; vague big-O answers fail signal tests. If asked to optimize, mention bidirectional BFS that grows the smaller frontier from each end. On whiteboard interviews, code the BFS first, run a tiny dry run, then add the DFS reconstruction so the interviewer sees you are decomposing the problem.

Follow-up Questions#

How would you adapt this to weighted edges? Replace BFS with Dijkstra and store predecessors in a min-heap-aware fashion. How do you parallelize the search? Bidirectional BFS is the practical answer; one frontier from beginWord, another from endWord, meet in the middle. What if the dictionary is enormous and changes daily? Index words by pattern keys like h*t so each word maps to L pattern buckets, reducing neighbor generation from O(26 times L) to O(L) per node. How would you stream just one shortest path instead of all? Standard Word Ladder I; you only need a parent pointer, not a parent set, and you can stop at the first endWord discovery.

Key Takeaways#

• Word Ladder II requires BFS for shortest distance plus a parent map for path reconstruction
• Remove the entire current layer from the dictionary in bulk to preserve sibling parent links
• Build neighbors lazily by character swap, not by precomputing the full edge list
• DFS the parents map backward from endWord to enumerate every shortest path
• Mention bidirectional BFS as an optimization in interviews
• The pattern generalizes to Open the Lock, Sliding Puzzle, and any implicit-graph shortest-path problem