126. Word Ladder II

Hash Table
String
Backtracking
Breadth-First Search

TIME

O(n L 26) for the BFS, plus the output size

SPACE

O(n * L)

Intuition

Words are nodes, one-letter differences are unit-weight edges, so shortest sequences are shortest paths. Enumerating all paths with plain DFS is hopeless; instead build the shortest-path DAG with BFS, then read all paths out of it.

BFS gives each reachable word its distance from beginWord. An edge cur -> next lies on a shortest path exactly when dist[next] == dist[cur] + 1, so recording those edges as parent links produces a DAG containing every shortest path and nothing else. Walking it backwards from endWord yields the answers without exploring a single dead end.

The one thing that needs care: a word can have several parents in the same BFS level's predecessor set. Removing visited words from the candidate set must happen after the whole level is processed, not on first discovery, or the second and later parents get lost.

Approach

Put wordList in a set. If endWord is absent, return [].
BFS from beginWord level by level. For each word in the current level, generate neighbours by replacing each position with the 25 other letters and keeping those still in the unvisited set.
- For each such neighbour, append the current word to parents[neighbour].
- Collect the level's discovered words, then remove them all from the unvisited set and make them the next level.
- Stop as soon as endWord appears in a level.
If endWord was never reached, return [].
DFS from endWord following parents down to beginWord, building each path in reverse and reversing it at the end.

Generating neighbours by mutation costs O(L * 26) per word, which beats comparing every pair of words when L <= 5.

Complexity

Time: O(n * L * 26) for the BFS plus O(total output size) for the path extraction
Space: O(n * L) for the parent graph, plus the output

Edge Cases

endWord not in wordList → [] (Example 2)
beginWord present in wordList → it must be excluded from the unvisited set up front, or it can be rediscovered as its own neighbour
beginWord and endWord one letter apart → a single two-word sequence
endWord unreachable although present → []
Words of length 1 (beginWord = "a", endWord = "c") → every pair of distinct letters differs in one position
Many parallel shortest paths: the output can be large, which is why the DAG must be traversed rather than the graph re-searched

Code

from collections import defaultdict
from string import ascii_lowercase
from typing import List


class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        """
        126. Word Ladder II
        Time: O(n * L * 26) for the BFS, plus the output size
        Space: O(n * L)
        """
        unvisited = set(wordList)
        if endWord not in unvisited:
            return []
        unvisited.discard(beginWord)

        parents = defaultdict(list)
        level = {beginWord}
        found = False

        while level and not found:
            discovered = set()
            for word in level:
                for i in range(len(word)):
                    prefix, suffix = word[:i], word[i + 1:]
                    for ch in ascii_lowercase:
                        if ch == word[i]:
                            continue
                        nxt = prefix + ch + suffix
                        if nxt in unvisited:
                            discovered.add(nxt)
                            # only shortest-path edges land here, since nxt is
                            # still unvisited and so sits on the next level
                            parents[nxt].append(word)
                            if nxt == endWord:
                                found = True
            # remove after the whole level, so every parent gets recorded
            unvisited -= discovered
            level = discovered

        if not found:
            return []

        result = []
        path = [endWord]

        def backtrack(word: str) -> None:
            if word == beginWord:
                result.append(path[::-1])
                return
            for prev in parents[word]:
                path.append(prev)
                backtrack(prev)
                path.pop()

        backtrack(endWord)
        return result

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 126. Word Ladder II
 * Time: O(n * L * 26) for the BFS, plus the output size
 * Space: O(n * L)
 */
class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Set<String> unvisited = new HashSet<>(wordList);
        List<List<String>> result = new ArrayList<>();
        if (!unvisited.contains(endWord)) {
            return result;
        }
        unvisited.remove(beginWord);

        Map<String, List<String>> parents = new HashMap<>();
        Set<String> level = new HashSet<>();
        level.add(beginWord);
        boolean found = false;

        while (!level.isEmpty() && !found) {
            Set<String> discovered = new HashSet<>();
            for (String word : level) {
                char[] chars = word.toCharArray();
                for (int i = 0; i < chars.length; i++) {
                    char original = chars[i];
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        if (ch == original) {
                            continue;
                        }
                        chars[i] = ch;
                        String next = new String(chars);
                        if (unvisited.contains(next)) {
                            discovered.add(next);
                            // only shortest-path edges land here, since next is
                            // still unvisited and so sits on the following level
                            parents.computeIfAbsent(next, key -> new ArrayList<>()).add(word);
                            if (next.equals(endWord)) {
                                found = true;
                            }
                        }
                    }
                    chars[i] = original;
                }
            }
            // remove after the whole level, so every parent gets recorded
            unvisited.removeAll(discovered);
            level = discovered;
        }

        if (!found) {
            return result;
        }

        List<String> path = new ArrayList<>();
        path.add(endWord);
        backtrack(endWord, beginWord, parents, path, result);
        return result;
    }

    private void backtrack(String word, String beginWord, Map<String, List<String>> parents,
                           List<String> path, List<List<String>> result) {
        if (word.equals(beginWord)) {
            List<String> done = new ArrayList<>(path);
            Collections.reverse(done);
            result.add(done);
            return;
        }
        for (String prev : parents.getOrDefault(word, Collections.emptyList())) {
            path.add(prev);
            backtrack(prev, beginWord, parents, path, result);
            path.remove(path.size() - 1);
        }
    }
}