115. Word Ladder

Two words are neighbours (one-letter apart) iff they match if you mask out one position with *. So we precompute, for every word and every position, the pattern that results from masking that position — and bucket all words by their patterns. Now finding all neighbours of a word costs O(M) lookups, not O(N) scans. BFS finds shortest paths, so the first time we reach endWord gives the minimum ladder length.

Why patterns are faster than pairwise comparison

Naive: for each word, compare with every other word and count differing letters. That's O(N · N · M) = O(N² M). Too slow for N up to a few thousand.

Pattern bucketing: each M-letter word produces M patterns (one per position, replace that letter with *). Two words are neighbours iff they share a pattern. So we precompute the buckets once (O(N · M²) time, since each pattern is O(M) to construct), and then each neighbour-lookup is O(M) patterns × constant per bucket.

Steps

1. Convert wordList to a set. If endWord isn't in the set, no ladder exists — return 0.
2. Build pattern buckets: for every word w and every index i, add w to buckets[w[:i] + '*' + w[i+1:]].
3. BFS: start with (beginWord, 1). Mark beginWord as visited.
4. While the queue is non-empty:
   • Pop (word, steps).
   • For each i in 0..M-1: compute the pattern word[:i] + '*' + word[i+1:]. For each nxt in buckets[pattern]:
     • If nxt == endWord, return steps + 1.
     • Else if nxt not in visited, mark visited and enqueue (nxt, steps + 1).
   • Optimisation: clear buckets[pattern] after processing — every word in that bucket has been or is now in the BFS frontier, so revisiting the bucket later wastes work.
5. If BFS exhausts without finding endWord, return 0.

Walk-through

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

Buckets after preprocessing (showing relevant ones):

BFS:

The shortest ladder is hit → hot → dot → dog → cog — 5 words.

Why BFS gives the shortest ladder

BFS explores nodes in non-decreasing distance order. The first time we touch endWord, the current steps + 1 is the shortest possible (any other path would have been popped earlier with a higher distance).

Edge cases

• endWord not in wordList: the early return.
• beginWord == endWord: the loop pops beginWord and finds it as a neighbour-of-itself in some bucket. Return 2 if it's in the list, else handle as no path. (Most variants assume distinct words.)
• Disconnected endWord: BFS exhausts; return 0.

Complexity

• Time: O(M² · N) — building buckets is O(N · M²) (each pattern is O(M) to build, M patterns per word). BFS visits each word once and inspects M patterns per word, each pattern triggers O(M) work to construct + walking the bucket.
• Space: O(M² · N) for the buckets.

import java.util.*;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> words = new HashSet<>(wordList);
        if (!words.contains(endWord)) return 0;
        int M = beginWord.length();
        Map<String, List<String>> buckets = new HashMap<>();
        for (String w : words) {
            for (int i = 0; i < M; i++) {
                String pattern = w.substring(0, i) + "*" + w.substring(i + 1);
                buckets.computeIfAbsent(pattern, k -> new ArrayList<>()).add(w);
            }
        }
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        Deque<String> queue = new ArrayDeque<>();
        queue.add(beginWord);
        int steps = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int s = 0; s < size; s++) {
                String word = queue.poll();
                for (int i = 0; i < M; i++) {
                    String pattern = word.substring(0, i) + "*" + word.substring(i + 1);
                    List<String> neighbors = buckets.getOrDefault(pattern, Collections.emptyList());
                    for (String nxt : neighbors) {
                        if (nxt.equals(endWord)) return steps + 1;
                        if (!visited.contains(nxt)) {
                            visited.add(nxt);
                            queue.add(nxt);
                        }
                    }
                    buckets.put(pattern, Collections.emptyList());
                }
            }
            steps++;
        }
        return 0;
    }
}