Word Ladder II

Problem Statement

Given a beginWord, an endWord, and a wordList, find all shortest transformation sequences from beginWord to endWord, where:

• Each transformation changes exactly one letter.
• Each intermediate word must exist in wordList.
• The beginWord does not need to be in wordList.

Example:

beginWord = "hit"
endWord   = "cog"
wordList  = ["hot", "dot", "dog", "lot", "log", "cog"]

Output:
[
  ["hit", "hot", "dot", "dog", "cog"],
  ["hit", "hot", "lot", "log", "cog"]
]

Both paths have length 5 — the shortest possible. The problem asks for every path that achieves this minimum length.

This is LeetCode 126 and consistently ranks among the hardest graph problems in interviews.

Why This Problem Is Hard

Word Ladder I asks for the length of the shortest transformation. Standard BFS handles it: enqueue beginWord, expand neighbors level by level, return the level when endWord appears. Straightforward.

Word Ladder II asks for all shortest transformation sequences. This requirement introduces three compounding difficulties:

1. Multiple shortest paths coexist. BFS naturally discovers one shortest path, but multiple words can appear at the same BFS level, each contributing a different route.
2. Path storage explodes. A naive approach that stores every partial path in the BFS queue consumes $O(P \cdot K)$ memory where $P$ is the number of shortest paths and $K$ is the path length — potentially millions of entries.
3. Re-visiting is subtle. Standard BFS marks nodes visited immediately. Here, a word discovered at level $d$ by one parent must remain accessible to other parents at the same level $d$, otherwise valid shortest paths get lost.

The solution decomposes the problem into two clean phases: BFS to discover shortest distances and build a directed acyclic graph (DAG), then DFS on the DAG to enumerate paths.

Key Insight: Build a DAG, Then Traverse It

The central idea:

1. Run BFS from beginWord. Record the distance (BFS level) at which each word is first reached.
2. During BFS, whenever a neighbor is at distance current + 1, add an edge current → neighbor. This creates a DAG — a directed acyclic graph containing only edges along shortest paths.
3. Run DFS from beginWord through this DAG. Every path that reaches endWord is guaranteed to be a shortest path.

The DAG eliminates all non-shortest edges. DFS can explore freely without worrying about path length — every route through the DAG is optimal by construction.

Step 1: Graph Modeling

Each word is a node. Two nodes share an edge when their words differ by exactly one character. Building the adjacency list naively — comparing every pair of words — costs $O(N^2 \cdot L)$, which is too slow for large word lists.

Optimization: pattern grouping. Replace each character position with a wildcard * to generate patterns. Words sharing a pattern are neighbors:

"hot" → ["*ot", "h*t", "ho*"]
"dot" → ["*ot", "d*t", "do*"]
"lot" → ["*ot", "l*t", "lo*"]

The pattern "*ot" groups ["hot", "dot", "lot"] — all mutual neighbors.

Map<String, List<String>> buildPatternMap(List<String> wordList) {
    var patternMap = new HashMap<String, List<String>>();
    for (String word : wordList) {
        char[] chars = word.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char original = chars[i];
            chars[i] = '*';
            String pattern = new String(chars);
            patternMap.computeIfAbsent(pattern, _ -> new ArrayList<>()).add(word);
            chars[i] = original;
        }
    }
    return patternMap;
}

This maps each pattern to all words matching it. Finding neighbors for a given word takes $O(L)$ pattern lookups, each returning a list of matches. Total preprocessing: $O(N \cdot L)$.

Step 2: BFS — Build Distance Map and DAG

BFS explores level by level from beginWord. Two data structures emerge:

• distance: maps each word to the BFS level at which it was first discovered.
• children: maps each word to the set of neighbors discovered at distance + 1 — the DAG edges.

A critical detail: when processing a word at level $d$, a neighbor at level $d + 1$ might already have been discovered (by another word at level $d$). The neighbor is not re-enqueued, but the edge is added to children. This captures all shortest-path relationships.

record BFSResult(Map<String, Integer> distance, Map<String, List<String>> children) {}

BFSResult bfs(String beginWord, String endWord, Map<String, List<String>> patternMap) {
    var distance = new HashMap<String, Integer>();
    var children = new HashMap<String, List<String>>();
    var queue = new ArrayDeque<String>();

    distance.put(beginWord, 0);
    queue.add(beginWord);
    boolean found = false;

    while (!queue.isEmpty() && !found) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            String current = queue.poll();
            int currentDist = distance.get(current);

            for (String neighbor : getNeighbors(current, patternMap)) {
                if (!distance.containsKey(neighbor)) {
                    distance.put(neighbor, currentDist + 1);
                    queue.add(neighbor);
                    if (neighbor.equals(endWord)) {
                        found = true;
                    }
                }
                if (distance.containsKey(neighbor) && distance.get(neighbor) == currentDist + 1) {
                    children.computeIfAbsent(current, _ -> new ArrayList<>()).add(neighbor);
                }
            }
        }
    }
    return new BFSResult(distance, children);
}

List<String> getNeighbors(String word, Map<String, List<String>> patternMap) {
    var neighbors = new ArrayList<String>();
    char[] chars = word.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        char original = chars[i];
        chars[i] = '*';
        String pattern = new String(chars);
        List<String> matches = patternMap.getOrDefault(pattern, List.of());
        for (String match : matches) {
            if (!match.equals(word)) {
                neighbors.add(match);
            }
        }
        chars[i] = original;
    }
    return neighbors;
}

BFS terminates once it finishes the level where endWord appears. No deeper levels need exploration — they cannot contain shorter paths.

Step 3: DFS Backtracking — Enumerate All Paths

With the DAG stored in children, DFS from beginWord collects every path to endWord. Each edge in children is guaranteed to advance along a shortest path, so no distance checks are needed during DFS.

List<List<String>> dfs(String beginWord, String endWord, Map<String, List<String>> children) {
    var results = new ArrayList<List<String>>();
    var path = new ArrayList<String>();
    path.add(beginWord);
    backtrack(beginWord, endWord, children, path, results);
    return results;
}

void backtrack(String current, String endWord, Map<String, List<String>> children,
               List<String> path, List<List<String>> results) {
    if (current.equals(endWord)) {
        results.add(new ArrayList<>(path));
        return;
    }
    List<String> nextWords = children.getOrDefault(current, List.of());
    for (String next : nextWords) {
        path.add(next);
        backtrack(next, endWord, children, path, results);
        path.removeLast();
    }
}

The path.removeLast() call is the backtracking step — it undoes the choice so the next sibling branch starts clean.

Complete Solution

Combining all three steps into one cohesive class:

import java.util.*;

public class WordLadderII {

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        var wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) {
            return List.of();
        }
        wordSet.add(beginWord);

        // Step 1: Build pattern map
        Map<String, List<String>> patternMap = buildPatternMap(wordSet);

        // Step 2: BFS to build DAG
        var distance = new HashMap<String, Integer>();
        var children = new HashMap<String, List<String>>();
        var queue = new ArrayDeque<String>();

        distance.put(beginWord, 0);
        queue.add(beginWord);
        boolean found = false;

        while (!queue.isEmpty() && !found) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String current = queue.poll();
                int currentDist = distance.get(current);

                for (String neighbor : getNeighbors(current, patternMap)) {
                    if (!distance.containsKey(neighbor)) {
                        distance.put(neighbor, currentDist + 1);
                        queue.add(neighbor);
                        if (neighbor.equals(endWord)) found = true;
                    }
                    if (distance.get(neighbor) == currentDist + 1) {
                        children.computeIfAbsent(current, _ -> new ArrayList<>()).add(neighbor);
                    }
                }
            }
        }

        if (!found) return List.of();

        // Step 3: DFS to enumerate paths
        var results = new ArrayList<List<String>>();
        var path = new ArrayList<String>();
        path.add(beginWord);
        backtrack(beginWord, endWord, children, path, results);
        return results;
    }

    private Map<String, List<String>> buildPatternMap(Set<String> wordSet) {
        var patternMap = new HashMap<String, List<String>>();
        for (String word : wordSet) {
            char[] chars = word.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                char original = chars[i];
                chars[i] = '*';
                patternMap.computeIfAbsent(new String(chars), _ -> new ArrayList<>()).add(word);
                chars[i] = original;
            }
        }
        return patternMap;
    }

    private List<String> getNeighbors(String word, Map<String, List<String>> patternMap) {
        var neighbors = new ArrayList<String>();
        char[] chars = word.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char original = chars[i];
            chars[i] = '*';
            for (String match : patternMap.getOrDefault(new String(chars), List.of())) {
                if (!match.equals(word)) neighbors.add(match);
            }
            chars[i] = original;
        }
        return neighbors;
    }

    private void backtrack(String current, String endWord, Map<String, List<String>> children,
                           List<String> path, List<List<String>> results) {
        if (current.equals(endWord)) {
            results.add(new ArrayList<>(path));
            return;
        }
        for (String next : children.getOrDefault(current, List.of())) {
            path.add(next);
            backtrack(next, endWord, children, path, results);
            path.removeLast();
        }
    }
}

Walkthrough

Tracing through the example with beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log", "cog"]:

Pattern Grouping:

Pattern	Words
*it	hit
h*t	hit, hot
hi*	hit
*ot	hot, dot, lot
ho*	hot
d*t	dot
do*	dot, dog
*og	dog, log, cog
d*g	dog
l*t	lot
lo*	lot, log
l*g	log
c*g	cog
co*	cog

BFS Levels:

Level	Words Discovered
0	hit
1	hot
2	dot, lot
3	dog, log
4	cog (endWord — stop)

DAG (children map):

hit → [hot]
hot → [dot, lot]
dot → [dog]
lot → [log]
dog → [cog]
log → [cog]

DFS Path Enumeration:

hit → hot → dot → dog → cog  ✓ (path 1)
hit → hot → lot → log → cog  ✓ (path 2)

Both paths have length 5, matching the BFS shortest distance.

Alternative: Bidirectional BFS

Standard BFS explores outward from beginWord in a sphere of radius $d$. The search space grows as $O(b^d)$ where $b$ is the branching factor.

Bidirectional BFS searches from both ends simultaneously:

• Maintain two frontiers: one from beginWord, one from endWord.
• Expand the smaller frontier at each step.
• Stop when the frontiers meet.

This reduces the effective search depth from $d$ to $d/2$, shrinking the explored space from $O(b^d)$ to $O(2 \cdot b^{d/2})$ — an exponential improvement.

The DAG construction and DFS enumeration remain the same; only the BFS phase changes. The implementation alternates which frontier to expand, building DAG edges from the beginWord side toward endWord.

Complexity Analysis

Phase	Time	Space
Pattern map	$O(N \cdot L)$	$O(N \cdot L)$
BFS	$O(N \cdot L^2)$	$O(N \cdot L)$
DFS	$O(P \cdot K)$	$O(P \cdot K)$
Total	$O(N \cdot L^2 + P \cdot K)$	$O(N \cdot L + P \cdot K)$

Where:

• $N$ = number of words in wordList
• $L$ = length of each word
• $P$ = number of shortest paths
• $K$ = length of each shortest path

The BFS neighbor lookup involves $L$ patterns, each generating up to $L$-length strings, hence $O(L^2)$ per word. The DFS phase is output-sensitive — it does work proportional to the answer size.

Edge Cases

Case	Handling
endWord not in wordList	Return empty list immediately — no path exists.
beginWord equals endWord	Return [[beginWord]] — zero transformations needed.
No transformation possible	BFS never reaches endWord; return empty list.
Large word lists	Pattern grouping keeps neighbor lookup at $O(L)$ per word; avoid $O(N)$ brute-force comparisons.
Multiple parents at same level	The distance.get(neighbor) == currentDist + 1 check ensures all parents are captured without re-enqueueing.
Single-character words	Works correctly — each pattern is "*", grouping all single-character words together.

Interviewer Tips

This ranks among the hardest BFS/DFS problems on LeetCode (Hard). The key phrase to communicate early:

“BFS finds the shortest distance and builds a DAG of shortest-path edges. DFS on the DAG enumerates all shortest paths.”

This signals that you understand the two-phase decomposition — the core insight interviewers look for.

Common follow-ups:

• Word Ladder I (warm-up): Return the length of the shortest transformation only. Pure BFS, no DAG needed.
• K shortest paths: Replace DFS with a priority queue (Yen’s algorithm or Eppstein’s algorithm).
• If words have different lengths: The one-letter-change constraint no longer applies; redefine the edit distance metric.

Optimization signals that show maturity:

• Pattern grouping instead of brute-force neighbor comparison.
• Processing BFS level by level (not word by word) to handle same-level parent relationships.
• Using removeLast() for backtracking instead of creating new list copies.