Word Ladder

Given two words begin and end of the same length and a dictionary, find the number of words in the shortest transformation sequence from begin to end, where:

each step changes exactly one letter, and
every word after begin must be in the dictionary (so end must be too).

Return 0 if there is no such sequence.

LeetCode: 127. Word Ladder

Example

Text

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

With "cog" missing from the dictionary: 0

Words are vertices, and two words are connected when they differ in exactly one letter. The shortest sequence is a shortest path in this unweighted graph, which is what breadth-first search finds.

Brute force: BFS, test every word for adjacency

For each word taken from the queue, compare it with every dictionary word that hasn't been visited yet.

Java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;

public class Main {
    static 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;
    }

    static int ladderLength(String begin, String end, List<String> dict) {
        boolean[] visited = new boolean[dict.size()];
        Deque<String> words = new ArrayDeque<>();
        Deque<Integer> stepsQueue = new ArrayDeque<>();
        words.add(begin);
        stepsQueue.add(1);
        while (!words.isEmpty()) {
            String word = words.poll();
            int steps = stepsQueue.poll();
            if (word.equals(end)) return steps;
            for (int i = 0; i < dict.size(); i++) {
                String next = dict.get(i);
                if (!visited[i] && oneApart(word, next)) {
                    visited[i] = true;
                    words.add(next);
                    stepsQueue.add(steps + 1);
                }
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        List<String> dict = List.of("hot", "dot", "dog", "lot", "log", "cog");
        System.out.println(ladderLength("hit", "cog", dict) + " " + ladderLength("hit", "cog", dict.subList(0, 5)));
    }
}

Output

5 0

Time: O(n² · L) for n dictionary words of length L: each dequeued word is compared with all n words. The queues hold at most n + 1 words. Space: O(n).

Optimal: generate the neighbours

A word of length L has only 25 · L possible one-letter variants. Generating them and checking each in a HashSet<String> is much cheaper than scanning the whole dictionary when n is large. Removing a word from the set when it's enqueued marks it as visited.

Java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    record Entry(char[] word, int steps) {}

    static int ladderLength(String begin, String end, List<String> dict) {
        Set<String> unvisited = new HashSet<>(dict);
        if (!unvisited.contains(end)) return 0;
        Deque<Entry> queue = new ArrayDeque<>();
        queue.add(new Entry(begin.toCharArray(), 1));
        while (!queue.isEmpty()) {
            Entry entry = queue.poll();
            char[] word = entry.word();
            if (new String(word).equals(end)) return entry.steps();
            for (int i = 0; i < word.length; i++) {
                char original = word[i];
                for (char c = 'a'; c <= 'z'; c++) {
                    word[i] = c;
                    if (unvisited.remove(new String(word))) {
                        queue.add(new Entry(word.clone(), entry.steps() + 1));
                    }
                }
                word[i] = original;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        List<String> dict = List.of("hot", "dot", "dog", "lot", "log", "cog");
        System.out.println(ladderLength("hit", "cog", dict) + " " + ladderLength("hit", "cog", dict.subList(0, 5)));
        System.out.println(ladderLength("a", "c", List.of("a", "b", "c")));
    }
}

Output

5 0
2

Time: O(n · L² · 26): for each of up to n words, 26 · L variants, each hashed in O(L). Space: O(n · L).

A char[] is mutable, unlike a String. Changing word[i] in place and restoring it afterwards avoids building a new array for every variant. new String(word) is built only to query the set, and a clone() is made only for variants that are actually enqueued. The queue holds a small record (Entry, a class with two read-only fields) that pairs the word with its step count.

Searching from both ends at once (bidirectional BFS) and always expanding the smaller frontier cuts the number of visited words further on large dictionaries.

Edge cases

end not in the dictionary: 0 immediately.
begin in the dictionary: harmless; at worst it's revisited once.
begin == end: 1, a sequence of one word.