Word Ladder II

Table of Contents +

Word Ladder II is the harder cousin of Word Ladder. The first version asked only for the length of the shortest chain. This one asks for every shortest chain itself. That small change makes the problem much deeper. Now you need both BFS and backtracking working together.

🎯 The Problem

You get a start word, an end word, and a word list, and must return every shortest transformation chain.

  • You turn the start word into the end word by changing one letter at a time.
  • Every step must stay a real word from the list. This part is exactly like Word Ladder.
  • The new twist is the output. You return every shortest chain, not just its length.
  • If two chains tie for shortest, you return both.
  • If no valid chain exists, return an empty list.

Let us say the start word is hit and the end word is cog. The word list is ["hot", "dot", "dog", "lot", "log", "cog"]. There are two shortest chains. One goes hit -> hot -> dot -> dog -> cog. The other goes hit -> hot -> lot -> log -> cog. Both have five words. So we return both.

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


Explanation: Both chains have 5 words and tie for shortest.

Here is the word graph. Notice hot splits into two branches that both reach cog in the same number of steps. That is why we get two answers.

hit

hot

dot

lot

dog

log

cog

🐢 Approach 1: List Every Path (Brute Force)

Walk every chain from start to end and keep the shortest ones.

The idea:

  • Try every path from the begin word to the end word.
  • Record the length of each one.
  • Filter for the minimum length and return those.

Why it is weak:

  • It explores a giant number of paths. Many are long dead ends.
  • The work grows out of control fast.
  • For any real word list this is far too slow. We need structure.

Here is the path-BFS code:

word_ladder_ii_path_bfs.py
from collections import deque
def find_ladders(begin_word, end_word, word_list):
    words, q, ans = set(word_list), deque([[begin_word]]), []
    while q and not ans:
        used = set()
        for _ in range(len(q)):
            path = q.popleft()
            if path[-1] == end_word:
                ans.append(path); continue
            for i in range(len(path[-1])):
                for ch in "abcdefghijklmnopqrstuvwxyz":
                    nxt = path[-1][:i] + ch + path[-1][i+1:]
                    if nxt in words:
                        used.add(nxt); q.append(path + [nxt])
        words -= used
    return ans

⚡ Approach 2: BFS for Length, Then DFS by Distance (Better)

The idea in one line: first measure the shortest distance with BFS, then build only paths that match it.

The idea:

  • Run a plain BFS to find the distance of every word from the begin word.
  • Then DFS forward from the begin word.
  • Only step to a neighbor whose distance is exactly one more than the current word.

Why it is better:

  • The distance check prunes every path that is not a shortest one.
  • So the DFS never wanders into long dead ends.
  • It returns all shortest chains, not just the length.

Why it is still not best:

  • It runs two passes: one BFS, then a separate DFS.
  • The forward DFS can re-explore shared prefixes of many chains.

Here is the BFS-distance plus DFS code:

word_ladder_ii_distance_dfs.py
from collections import deque, defaultdict
def find_ladders(begin_word, end_word, word_list):
    words, graph, dist = set(word_list), defaultdict(list), {begin_word: 0}
    q = deque([begin_word])
    while q:
        word = q.popleft()
        for i in range(len(word)):
            for ch in "abcdefghijklmnopqrstuvwxyz":
                nxt = word[:i] + ch + word[i+1:]
                if nxt in words:
                    graph[word].append(nxt)
                    if nxt not in dist:
                        dist[nxt] = dist[word] + 1; q.append(nxt)
    ans = []
    def dfs(word, path):
        if word == end_word: ans.append(path[:]); return
        for nxt in graph[word]:
            if dist.get(nxt) == dist[word] + 1: dfs(nxt, path + [nxt])
    dfs(begin_word, [begin_word])
    return ans

🚀 Approach 3: BFS for Parents, Then Backtrack (Best)

The idea in one line: BFS records each word’s parents, then backtracking walks those parents to rebuild every chain.

The idea:

  • Run BFS level by level from the begin word.
  • For each word, record who reached it on its shortest level. Those are its parents.
  • A parent of a word is a word one step before it on a shortest chain.
  • A word can have many parents. That is how you capture every branch.

How it works:

  • Spread out level by level, building a parent map.
  • Only remove words from the unused set after a whole level finishes, not during it.
  • This matters because two words on the same level can both be valid parents of the same next word.
  • After BFS, backtrack: walk backward from the end word through the parents to the begin word.
  • Reverse each traced path so it reads start to end. Each one is a shortest chain.

Why it is best:

  • BFS visits each word once, same cost as plain Word Ladder.
  • The parent map lets backtracking rebuild every chain without re-searching.
  • No path is wasted on a non-shortest route.

Here is the parent map BFS builds. Arrows point from a word back to its parents.

cog

dog

log

dot

lot

hot

hit

Steps to Solve

  1. Put the word list into a set for instant lookup.
  2. Run BFS level by level from the begin word. Track the distance of each word.
  3. For each word reached on its shortest level, store every parent that reached it.
  4. After each level, remove all words used in that level from the unused set.
  5. Stop BFS once you reach the end word’s level.
  6. Backtrack from the end word through the parents to the begin word.
  7. Reverse each traced path and collect it as one shortest chain.

This Python version uses a defaultdict of parents and a recursive backtrack. It is the cleanest of the five.

word_ladder_ii.py
from collections import defaultdict




def find_ladders(begin, end, word_list):
    words = set(word_list)
    if end not in words:
        return []


    parents = defaultdict(list)   # word -> who reached it on the shortest level
    level = {begin}
    words.discard(begin)
    found = False


    while level and not found:
        next_level = set()
        words -= level            # remove the whole level at once
        for word in level:
            for i in range(len(word)):
                for c in "abcdefghijklmnopqrstuvwxyz":
                    cand = word[:i] + c + word[i + 1:]
                    if cand in words:
                        next_level.add(cand)
                        parents[cand].append(word)   # record the parent
                        if cand == end:
                            found = True
        level = next_level


    res = []


    def backtrack(word, path):
        if word == begin:
            res.append([begin] + path[::-1])   # reverse to read start to end
            return
        for p in parents[word]:
            backtrack(p, path + [word])


    if found:
        backtrack(end, [])
    return res




word_list = ["hot", "dot", "dog", "lot", "log", "cog"]
for chain in find_ladders("hit", "cog", word_list):
    print(" -> ".join(chain))

The output of the above code will be:

hit -> hot -> dot -> dog -> cog
hit -> hot -> lot -> log -> cog

Let us read the Python version line by line. Code first, then the why.

We begin with words = set(word_list) for instant lookups. Then if end not in words: return [] because no chain is possible without the end word.

parents = defaultdict(list) is the heart of the trick. For each word it holds the list of words that reached it on its shortest level. A defaultdict gives an empty list the first time we touch a new key, so we never check for missing keys.

level = {begin} is the current BFS frontier. The frontier is the set of words we just reached. We seed it with the begin word. words.discard(begin) removes the begin word so we do not revisit it.

The loop runs while level and not found. We stop the moment a level contains the end word. There is no point searching deeper, because deeper means longer chains.

words -= level removes the entire current frontier at once, after we picked it up but before scanning neighbors. This is the careful rule. If we deleted words one by one inside the scan, two parents on the same level could not both claim the same child.

The three inner loops build candidates by swapping each letter. if cand in words checks the candidate is real and not yet used in an earlier level. We then add it to next_level and append the current word to parents[cand]. If the candidate is the end word we set found = True.

After BFS, backtrack(end, []) walks the parents backward. Each call prepends the path. When it reaches the begin word, res.append([begin] + path[::-1]) reverses the path so it reads start to end. Because a word can have many parents, the recursion naturally branches into every shortest chain.

⏱️ Time and Space Complexity

The BFS phase costs the same as plain Word Ladder, about O(n * L * 26) where n is the word count and L is the word length. The backtracking phase costs extra because it builds every shortest chain, and there can be many. So the total time depends on how many answers exist. The space holds the parent map and the recursion, which is O(n * L) plus the size of the output.

Approach Time Complexity Space Complexity
List every path (brute force) Exponential O(n * L)
BFS for length plus DFS by distance O(n * L * 26) plus output size O(n * L) plus output
BFS for parents plus backtracking O(n * L * 26) plus output size O(n * L) plus output

Tip

The trap in this problem is deleting visited words too early. Remove a whole level at once, after you read it, not during the scan. Otherwise you lose valid parents and miss some chains.

🧩 Key Takeaways

  • ✅ Word Ladder II returns every shortest chain, not just its length.
  • ✅ Run BFS first to find the shortest level and record each word’s parents.
  • ✅ A word can have several parents, which is how you capture every branch.
  • ✅ Remove a whole level at once so two same-level parents both stay valid.
  • ✅ Backtrack through the parents from end to begin, then reverse each path.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    How is Word Ladder II different from Word Ladder?

    Why: Word Ladder asks for the length. Word Ladder II asks for all the shortest chains themselves.

  2. 2

    What does the parents map store?

    Why: Each word records its parents, the words one step before it on a shortest chain, which lets backtracking rebuild every path.

  3. 3

    Why must we remove a whole level at once instead of word by word?

    Why: Deleting during the scan would block one of two valid same-level parents and lose a shortest chain.

  4. 4

    What does backtracking do after BFS finishes?

    Why: Backtracking follows parents backward from the end word, and reversing each traced path gives a shortest chain start to end.

Score: 0 / 4

🚀 What’s Next?

Previous Word Ladder Next Accounts Merge