Word Ladder — BFS Over Wildcard-Pattern Buckets

Word Ladder is the canonical example of a problem where the graph is not given to you. You have to see one. Words are nodes, single-letter substitutions are edges, and shortest path is BFS. The interesting design choice is how you enumerate neighbors fast enough to survive a large word list.

The Problem

Given two words beginWord and endWord and a dictionary wordList, return the length of the shortest transformation sequence from beginWord to endWord such that:

• Only one letter changes per step.
• Every intermediate word is in wordList.
• beginWord does not need to be in wordList, but endWord does.

Return 0 if no such sequence exists. The length includes both endpoints.

Intuition

Naive neighbor generation scans the entire dictionary per word: O(N * L) per node, O(N^2 * L) total. Precompute a map from wildcard pattern to words instead. For each word of length L, generate L patterns by replacing each position with * and put the word into a bucket per pattern. Two words share a bucket exactly when they differ in one position. BFS guarantees the first time you pop endWord is the shortest ladder.

Explanation with Example

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

• Build buckets: "*ot" -> ["hot", "dot", "lot"], "h*t" -> ["hot"], "do*" -> ["dot", "dog"], and so on.
• BFS from hit with distance 1.
  • Patterns for hit: only "h*t" -> "hot". Enqueue (hot, 2).
• Pop hot. Patterns reach "dot", "lot". Enqueue (dot, 3), (lot, 3).
• Pop dot. Patterns yield "dog". Enqueue (dog, 4).
• Pop lot. Patterns yield "log". Enqueue (log, 4).
• Pop dog. "*og" leads to "cog". Enqueue (cog, 5).
• Pop cog. Match. Return 5.

layer 1:  hit
          |
layer 2:   hot
         / \
layer 3: dot   lot
        |     |
layer 4: dog   log
         \  /
layer 5:    cog   <-- endWord found at distance 5

each edge = one letter change; BFS guarantees minimum layer.

Code

from collections import deque, defaultdict

def ladderLength(beginWord, endWord, wordList):
    words = set(wordList)
    if endWord not in words:
        return 0
    L = len(beginWord)
    buckets = defaultdict(list)
    for w in words:
        for i in range(L):
            buckets[w[:i] + "*" + w[i+1:]].append(w)

    q = deque([(beginWord, 1)])
    visited = {beginWord}
    while q:
        word, dist = q.popleft()
        if word == endWord:
            return dist
        for i in range(L):
            pat = word[:i] + "*" + word[i+1:]
            for nbr in buckets[pat]:
                if nbr not in visited:
                    visited.add(nbr)
                    q.append((nbr, dist + 1))
            buckets[pat] = []  # avoid revisiting via this pattern
    return 0

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

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> words(wordList.begin(), wordList.end());
    if (!words.count(endWord)) return 0;
    int L = beginWord.size();
    unordered_map<string, vector<string>> buckets;
    for (auto& w : words) {
        for (int i = 0; i < L; i++) {
            string pat = w.substr(0, i) + "*" + w.substr(i + 1);
            buckets[pat].push_back(w);
        }
    }
    queue<pair<string,int>> q;
    q.push({beginWord, 1});
    unordered_set<string> visited{beginWord};
    while (!q.empty()) {
        auto [word, dist] = q.front(); q.pop();
        if (word == endWord) return dist;
        for (int i = 0; i < L; i++) {
            string pat = word.substr(0, i) + "*" + word.substr(i + 1);
            for (auto& nbr : buckets[pat]) {
                if (visited.insert(nbr).second) q.push({nbr, dist + 1});
            }
            buckets[pat].clear();
        }
    }
    return 0;
}

Edge Cases

• endWord not in dictionary — return 0 up front. This avoids wasted BFS.
• beginWord == endWord — by problem convention, the answer is 1, though some interview variants treat this as 0. Clarify before coding.
• Empty word list — return 0.
• Multiple shortest ladders — return the length; the path itself is a separate problem.

Complexity Analysis

Let N be the dictionary size and L the word length. Bucket construction is O(N * L^2) — there are L patterns per word and each pattern is built in O(L). BFS visits each word at most once and inspects L patterns per pop, each touching a bucket of total size bounded by O(N). Time bound: O(N * L^2). Space is O(N * L^2) for the bucket map.

Bidirectional BFS — run BFS from both ends and stop when the frontiers meet — cuts the explored set roughly square root in size. Worth mentioning in interviews, though the implementation has more moving parts.

How to Explain It in an Interview

Start by saying the words form an implicit graph: edge if they differ by one letter, shortest path by BFS. Then volunteer the cost problem: “Neighbor generation is the bottleneck — naive scan is O(N) per node. I’ll preprocess wildcard patterns so neighbor lookup is O(L) per node.” Sketch the bucket map. Mention the bucket-clearing optimization.

If the interviewer asks “can you do better,” answer bidirectional BFS. If they ask about all shortest ladders, say the BFS becomes a layered graph and the reconstruction is the hard part.

Related Problems

• Word Ladder II (return every shortest sequence)
• Minimum Genetic Mutation (same structure, smaller alphabet)
• Open the Lock (BFS on strings with single-position changes)
• Bus Routes (BFS on a constructed graph)

The last one is a great follow-up because it forces you to design a different node type from the obvious one.

Wrap up

Word Ladder is the test of whether you can see the graph that is not drawn. The wildcard bucket is the tactical insight; the strategic insight is BFS for shortest path on unweighted graphs. Pair this problem with BFS and DFS and you have a complete answer to half of the graph problems on a typical interview list.