Topics › Graphs › Problems on BFS/DFS

Word ladder II

Hard TUF ID 510 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given beginWord, endWord and a list wordList. A ladder is a sequence beginWord -> s1 -> ... -> sk where neighbouring words differ in exactly one letter, every si is in wordList (beginWord need not be), and sk == endWord. Return all shortest ladders, each as a list of words, in any order. Return an empty list if no ladder exists.

Constraints: all words have the same length L ≤ 5, lowercase letters, up to 500 distinct list words, beginWord != endWord. LeetCode also promises that the total number of answers is reasonable; the number of shortest ladders can otherwise be exponential.

Example 1

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

Example 2

beginWord = "red", endWord = "tax", wordList = [ted, tex, red, tax, tad, den, rex, pee]
answer = [[red, ted, tad, tax],
          [red, ted, tex, tax],
          [red, rex, tex, tax]]

Note that tex appears in two different answers, reached once from ted and once from rex.

Think of words as vertices and connect two words when they differ in one letter; a ladder is then a path, and BFS finds shortest paths in such an unweighted graph. Now we need not one shortest path but every shortest path, and that changes how visited words can be handled.

Approach 1: Brute force, DFS over all simple ladders

Intuition. Enumerate every ladder that never repeats a word, and keep the shortest ones. A small pruning helps: once some ladder of length k is known, any partial ladder longer than k can be abandoned. It is still exponential, because the number of simple paths in a graph can be exponential, but it is a correct reference to test the clever versions against.

Algorithm.

1. If endWord is not in the list, return an empty list.
2. DFS from beginWord, carrying the current path and a set onPath to forbid repeats.
3. On reaching endWord: if the path is shorter than the best so far, clear the answers; then record the path.
4. Try every list word that differs in one letter and is not on the path.

static List<List<String>> bruteForce(String beginWord, String endWord, List<String> wordList) {
    List<List<String>> best = new ArrayList<>();
    if (!wordList.contains(endWord)) return best;
    List<String> path = new ArrayList<>(List.of(beginWord));
    Set<String> onPath = new HashSet<>(path);
    explore(beginWord, endWord, wordList, path, onPath, best);
    return best;
}

static void explore(String word, String endWord, List<String> words, List<String> path,
                    Set<String> onPath, List<List<String>> best) {
    if (!best.isEmpty() && path.size() > best.get(0).size()) return;   // already longer than the best ladder
    if (word.equals(endWord)) {
        if (!best.isEmpty() && path.size() < best.get(0).size()) best.clear();
        best.add(new ArrayList<>(path));
        return;
    }
    for (String next : words) {
        if (!onPath.contains(next) && differByOne(word, next)) {
            path.add(next);
            onPath.add(next);
            explore(next, endWord, words, path, onPath, best);
            path.remove(path.size() - 1);
            onPath.remove(next);
        }
    }
}

static boolean differByOne(String a, String b) {
    if (a.length() != b.length()) return false;
    int diff = 0;
    for (int i = 0; i < a.length() && diff < 2; i++) {
        if (a.charAt(i) != b.charAt(i)) diff++;
    }
    return diff == 1;
}

Complexity. Time exponential in the worst case, since every simple path may be explored. Space O(N · L) for the path and the recursion.

Approach 2: BFS whose queue holds whole ladders

Intuition. BFS explores ladders in order of length, so the first level that reaches endWord contains exactly the shortest ladders. Store the entire ladder in each queue entry instead of a single word.

The subtle part is when to mark a word as used. When only the length is needed, a word can be removed from the dictionary the moment it is enqueued. Here that would be wrong: in Example 2, tex is reached at level 3 from both ted and rex, and removing it after ted uses it would lose the ladder red, rex, tex, tax. So the words used on a level are collected in usedThisLevel and removed only after the whole level is done. Removing them then is safe: any later ladder reaching such a word would be longer than the ones already queued.

Algorithm.

1. Start the queue with the ladder [beginWord]; remove beginWord from the dictionary.
2. Process one level at a time. For each ladder, if its last word is endWord, add it to the result. Otherwise extend it by every dictionary word one letter away, and remember those words.
3. After the level, remove all remembered words from the dictionary. Stop after the first level that produced a result.

static List<List<String>> bfsPaths(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);
    Deque<List<String>> q = new ArrayDeque<>();
    q.offer(new ArrayList<>(List.of(beginWord)));
    while (!q.isEmpty() && result.isEmpty()) {
        List<String> usedThisLevel = new ArrayList<>();
        for (int size = q.size(); size > 0; size--) {
            List<String> seq = q.poll();
            String last = seq.get(seq.size() - 1);
            if (last.equals(endWord)) { result.add(seq); continue; }
            char[] w = last.toCharArray();
            for (int i = 0; i < w.length; i++) {
                char original = w[i];
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    w[i] = ch;
                    String next = new String(w);
                    if (unvisited.contains(next)) {
                        List<String> longer = new ArrayList<>(seq);
                        longer.add(next);
                        q.offer(longer);
                        usedThisLevel.add(next);
                    }
                }
                w[i] = original;
            }
        }
        unvisited.removeAll(usedThisLevel);          // only now: ladders on the same level may share a word
    }
    return result;
}

Complexity. Correct, but the queue stores complete ladders, and the number of partial ladders can grow exponentially with the depth even when the final answer is small. Each copy costs O(depth). This is the version that runs out of time or memory on LeetCode’s harder tests.

Approach 3: Optimal, BFS for depths, then backtrack from the end

Intuition. Split the job in two. First, an ordinary BFS from beginWord records depth[w], the number of steps on the shortest ladder from beginWord to w. Stop as soon as endWord receives a depth, since deeper words cannot appear on a shortest ladder.

Second, observe that a ladder is shortest exactly when the depths along it go 0, 1, 2, ..., D with D = depth[endWord]. So we can rebuild every shortest ladder by walking backwards from endWord, at each step moving only to a one-letter neighbour whose depth is exactly one less.

Why backwards? Every word with depth k ≥ 1 was discovered from some word with depth k - 1, so a backward step is always available and every branch of the backtracking reaches beginWord. No work is wasted on dead ends. Walking forwards from beginWord, by contrast, many branches lead to words that never reach endWord.

Algorithm.

1. BFS from beginWord, storing depth for each newly discovered word, until endWord has a depth or the queue empties.
2. If endWord was never reached, return an empty list.
3. Backtrack from endWord: for each one-letter variation prev with depth[prev] == depth[word] - 1, add it to the path and recurse. When the current word is beginWord, reverse the path and record it.

static List<List<String>> optimal(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, Integer> depth = new HashMap<>();
    depth.put(beginWord, 0);
    Deque<String> q = new ArrayDeque<>();
    q.offer(beginWord);
    while (!q.isEmpty() && !depth.containsKey(endWord)) {
        String word = q.poll();
        int d = depth.get(word);
        char[] w = word.toCharArray();
        for (int i = 0; i < w.length; i++) {
            char original = w[i];
            for (char ch = 'a'; ch <= 'z'; ch++) {
                w[i] = ch;
                String next = new String(w);
                if (unvisited.remove(next)) {
                    depth.put(next, d + 1);
                    q.offer(next);
                }
            }
            w[i] = original;
        }
    }
    if (!depth.containsKey(endWord)) return result;
    List<String> path = new ArrayList<>(List.of(endWord));
    backtrack(endWord, beginWord, depth, path, result);
    return result;
}

static void backtrack(String word, String beginWord, Map<String, Integer> depth,
                      List<String> path, List<List<String>> result) {
    if (word.equals(beginWord)) {
        List<String> seq = new ArrayList<>(path);
        Collections.reverse(seq);                    // path was built from endWord backwards
        result.add(seq);
        return;
    }
    int d = depth.get(word);
    char[] w = word.toCharArray();
    for (int i = 0; i < w.length; i++) {
        char original = w[i];
        for (char ch = 'a'; ch <= 'z'; ch++) {
            w[i] = ch;
            String prev = new String(w);
            Integer pd = depth.get(prev);
            if (pd != null && pd == d - 1) {         // one level closer to beginWord
                path.add(prev);
                backtrack(prev, beginWord, depth, path, result);
                path.remove(path.size() - 1);
            }
        }
        w[i] = original;
    }
}

Dry run on Example 2. BFS assigns:

den and pee are never reached. Backtracking from tax (depth 3) finds tad and tex at depth 2. From tad the only depth-1 neighbour is ted; from tex there are two, ted and rex. All three branches end at red, giving exactly the three answers.

Complexity. The BFS costs O(N · 26 · L^2), as in Word Ladder I. The backtracking costs O(P · D · 26 · L) where P is the number of shortest ladders and D their length: it is proportional to the size of the output, which is the best possible since every answer has to be written out. Space O(N · L) for the depth map, plus the output.

Edge cases and pitfalls

• Removing words too early. Marking a word visited as soon as one ladder uses it drops other shortest ladders through the same word. Mark per level, or use the depth map.
• endWord missing. Return an empty list straight away.
• beginWord in the list. Remove it from the dictionary before the BFS. Otherwise Approach 3 rediscovers it at depth 2 and overwrites its depth 0, and the backtracking can never finish at it.
• Stopping the BFS. Stop after the level that reaches endWord. Continuing is not wrong in Approach 3, but it wastes time; in Approach 2 continuing would add longer ladders.
• Output order. Any order is accepted, so the tests sort the ladders before comparing.

Related problems

• Word ladder I only needs the length, so plain BFS with eager marking suffices.
• Shortest path in DAG works on the kind of layered graph that the depth map creates.
• Number of ways to arrive at destination counts shortest paths instead of listing them.
• Shortest path in undirected graph with unit weights is the BFS that the depth computation is built on.