Word Ladder

NeetCode: Word Ladder · LeetCode: 127. Word Ladder · Difficulty: Hard

Given beginWord, endWord and a wordList, return the number of words in the shortest sequence beginWord -> ... -> endWord where consecutive words differ in exactly one letter and every word after the first is in wordList. Return 0 if no such sequence exists. beginWord and endWord are different. All words have the same length and consist of lowercase letters.

Example

Text

begin = "hit", end = "cog", list = [hot, dot, dog, lot, log, cog]
Output: 5     (hit -> hot -> dot -> dog -> cog)

begin = "hit", end = "cog", list = [hot, dot, dog, lot, log]
Output: 0     ("cog" is not in the list)

Words are nodes, and two words are joined by an edge when they differ in one letter. The shortest path in an unweighted graph is found by BFS; the remaining work is finding a word's neighbors quickly.

Brute force: BFS comparing every pair of words

Put beginWord at index 0 and the list after it. During BFS, find the neighbors of a word by comparing it with every other word and keeping those that differ in exactly one position. ArrayDeque is Java's queue.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    // True when the words differ in exactly one position.
    private boolean oneApart(String a, String b) {
        int diff = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                diff++;
            }
        }
        return diff == 1;
    }

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        List<String> words = new ArrayList<>();
        words.add(beginWord);
        words.addAll(wordList);
        // Index of endWord in `words` (skip index 0, the begin word).
        int target = -1;
        for (int i = 1; i < words.size(); i++) {
            if (words.get(i).equals(endWord)) {
                target = i;
                break;
            }
        }
        if (target == -1) {
            return 0;
        }
        // dist[i] = words on the path from begin to words[i]; 0 means not reached yet.
        int[] dist = new int[words.size()];
        dist[0] = 1;
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        queue.add(0);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            if (cur == target) {
                return dist[cur];
            }
            for (int next = 0; next < words.size(); next++) {
                if (dist[next] == 0 && oneApart(words.get(cur), words.get(next))) {
                    dist[next] = dist[cur] + 1;
                    queue.add(next);
                }
            }
        }
        return 0;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        List<String> list = Arrays.asList("hot", "dot", "dog", "lot", "log", "cog");
        System.out.println(s.ladderLength("hit", "cog", list));
        System.out.println(s.ladderLength("hit", "cog", list.subList(0, 5)));
        System.out.println(s.ladderLength("a", "c", Arrays.asList("a", "b", "c")));
    }
}

Output

5
0
2

dist[next] == 0 doubles as the visited marker because real distances start at 1. Strings are compared with equals, not ==, because == on two String objects compares references. Time: O(N^2 * L) for N words of length L: each of the N dequeued words is compared with all N words at O(L) per comparison. Space: O(N) for the distances and queue.

Optimal: BFS through wildcard pattern buckets

Two words that differ in one letter share a pattern: the word with that letter replaced by a wildcard. hot, dot and lot all match *ot. Build a map from each pattern (*ot, h*t, ho*) to the words that match it. The neighbors of a word are the words in the buckets of its L patterns, so no pair comparison is needed. After a bucket is expanded, all its words are queued, so it is removed from the map and never scanned again.

Trace for hit -> cog with the first example: hit has patterns *it, h*t, hi*; only h*t has a bucket, giving hot (2 words). hot has *ot giving dot, lot (3), and h*t is already removed. dot reaches dog (4) through do*; lot reaches log through lo*. dog reaches cog through *og (5), and BFS returns 5.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

class Solution {
    // "hot" -> ["*ot", "h*t", "ho*"]
    private List<String> patterns(String word) {
        List<String> result = new ArrayList<>();
        char[] chars = word.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char saved = chars[i];
            chars[i] = '*';
            result.add(new String(chars));
            chars[i] = saved;
        }
        return result;
    }

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)) {
            return 0;
        }
        Map<String, List<String>> buckets = new HashMap<>();
        for (String word : wordList) {
            for (String p : patterns(word)) {
                buckets.computeIfAbsent(p, k -> new ArrayList<>()).add(word);
            }
        }
        // BFS queue holds {word, words on the path so far}.
        Set<String> seen = new HashSet<>();
        seen.add(beginWord);
        ArrayDeque<Object[]> queue = new ArrayDeque<>();
        queue.add(new Object[]{beginWord, 1});
        while (!queue.isEmpty()) {
            Object[] cur = queue.poll();
            String word = (String) cur[0];
            int steps = (Integer) cur[1];
            if (word.equals(endWord)) {
                return steps;
            }
            for (String p : patterns(word)) {
                List<String> neighbors = buckets.remove(p);
                if (neighbors != null) {
                    for (String next : neighbors) {
                        if (seen.add(next)) {
                            queue.add(new Object[]{next, steps + 1});
                        }
                    }
                }
            }
        }
        return 0;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        List<String> list = Arrays.asList("hot", "dot", "dog", "lot", "log", "cog");
        System.out.println(s.ladderLength("hit", "cog", list));
        System.out.println(s.ladderLength("hit", "cog", list.subList(0, 5)));
        System.out.println(s.ladderLength("a", "c", Arrays.asList("a", "b", "c")));
    }
}

Output

5
0
2

HashMap.remove returns the removed value, or null when the key is absent, so one call both checks for a bucket and takes it. HashSet.add returns false when the element is already present. Building the buckets costs O(N * L) pattern strings of length L, so O(N * L^2) character work. The BFS then touches each bucket once and each word once, with L pattern lookups per word, for the same O(N * L^2) total. This replaces the N^2 pair comparisons, which matters because L is small (at most 10 in the problem) while N can be thousands. Time: O(N * L^2). Space: O(N * L^2) for the buckets.

Edge cases

endWord missing from the list: return 0 immediately.
beginWord need not be in the list; it is only the start of the path.
The answer counts words, not edges, so a single step gives 2.

How to explain it in an interview

Model words as nodes and one-letter differences as edges; the shortest ladder is a BFS in an unweighted graph.
Comparing every pair of words per node costs O(N^2 * L).
Group words by wildcard pattern (h*t); words in the same bucket are neighbors.
BFS looks up each word's L patterns, and each bucket is expanded once, giving O(N * L^2) time and space.
Return the BFS level (counted in words) when endWord is dequeued, or 0 if the queue empties.