Word Ladder

1. Problem & Core Objective

Given beginWord, endWord, and a wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, where each step changes exactly one letter and every intermediate word must be in wordList. Return 0 if no sequence exists.

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

wordList without "cog"  →  0

Constraints: 1 <= word.length <= 10 · 1 <= wordList.length <= 5000 · all words the same length, lowercase · beginWord need not be in the list

What's actually being tested: two things, and the second is where most solutions fail. Recognising shortest path in an unweighted graph → BFS, and realising that building the adjacency efficiently is the real bottleneck — comparing every pair of words is O(N² · L), which dominates the BFS itself.

2. First-Principles Thought Process

The graph is implicit

Each word is a node. Two words are adjacent when they differ in exactly one letter.

Why BFS and not DFS or Dijkstra

Every transformation costs the same — one step. So the shortest sequence is the one with the fewest edges, and BFS explores strictly in order of edge count.

The first time BFS reaches endWord, that's the minimum; no later route can be shorter. DFS would find a path but not necessarily the shortest, and Dijkstra's priority queue is unnecessary overhead when all weights are 1.

The real bottleneck is the adjacency

The obvious neighbour test is "compare this word against every other word". That's O(N) comparisons of O(L) each per word, so O(N² · L) to explore the graph — at N = 5000, L = 10 that's 2.5 × 10^8.

The fix is wildcard buckets. Precompute a map from patterns to words:

"hot" → buckets "*ot", "h*t", "ho*"

Two words are neighbours exactly when they share a bucket. Generating a word's L patterns is O(L²) (each pattern is a new L-character string), so building the map is O(N · L²) = 5 × 10^5.

That's the difference between 2.5 × 10^8 and 5 × 10^5 — roughly 500×, and it's why this is rated Hard.

Counting words, not steps

The answer is the number of words in the sequence, so hit → hot → dot → dog → cog is 5, not 4. Start the level counter at 1 for beginWord.

The marking discipline

Remove a word from the unvisited set when it's enqueued, not when dequeued — otherwise the same word enters the queue from several neighbours in the same level, and the queue balloons.

3. Solution Paths

Approach 1 — BFS comparing every pair (brute force)

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> unvisited = new HashSet<>(wordList);
    if (!unvisited.contains(endWord)) return 0;

    Queue<String> q = new ArrayDeque<>();
    q.offer(beginWord);
    int level = 1;

    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            String word = q.poll();
            if (word.equals(endWord)) return level;

            Iterator<String> it = unvisited.iterator();
            while (it.hasNext()) {
                String candidate = it.next();
                if (differsByOne(word, candidate)) {      // O(L) against EVERY word
                    it.remove();
                    q.offer(candidate);
                }
            }
        }
        level++;
    }
    return 0;
}

• Time O(N² · L) · Space O(N · L)

Counter-questions on this approach

⭐ "The BFS is optimal. Where does the cost go?"

Into finding neighbours. For each word dequeued, it scans the entire unvisited set and does an O(L) comparison against each — so the total is O(N² · L).

At N = 5000 and L = 10 that's 2.5 × 10^8 character comparisons. The BFS itself visits at most N nodes; the adjacency discovery dominates it by orders of magnitude.

⭐ "So what's the fix?"

Precompute the adjacency instead of rediscovering it. Two words differ by one letter exactly when they match some pattern with one position wildcarded — "hot" and "dot" both match "*ot".

Bucketing every word under its L patterns costs O(N · L²) once, and then a word's neighbours are found by looking up its own L patterns. 5 × 10^5 instead of 2.5 × 10^8.

"Why it.remove() rather than a separate visited set?"

Removing from unvisited is the visited marker, and it shrinks the set being scanned. It's a genuine optimisation for this version — but it's fixing the symptom, since the scan shouldn't exist at all.

"Would checking endWord at enqueue instead of dequeue help?"

It saves one level of expansion — you'd return as soon as endWord is produced rather than when it comes off the queue. A constant-factor improvement, and the level arithmetic shifts by one. Correct either way as long as it's consistent.

Approach 2 — BFS with wildcard buckets (optimal)

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> words = new HashSet<>(wordList);
    if (!words.contains(endWord)) return 0;                  // unreachable by definition

    int L = beginWord.length();
    Map<String, List<String>> buckets = new HashMap<>();
    for (String w : wordList)
        for (int i = 0; i < L; i++) {
            String pattern = w.substring(0, i) + '*' + w.substring(i + 1);
            buckets.computeIfAbsent(pattern, k -> new ArrayList<>()).add(w);
        }

    Queue<String> q = new ArrayDeque<>();
    Set<String> visited = new HashSet<>();
    q.offer(beginWord);
    visited.add(beginWord);
    int level = 1;                                            // beginWord counts as word 1

    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            String word = q.poll();
            if (word.equals(endWord)) return level;

            for (int j = 0; j < L; j++) {
                String pattern = word.substring(0, j) + '*' + word.substring(j + 1);
                for (String next : buckets.getOrDefault(pattern, List.of())) {
                    if (visited.add(next)) q.offer(next);      // add returns false if present
                }
            }
        }
        level++;
    }
    return 0;
}

Trace — "hit" → "cog":

• Time O(N · L²) to build, O(N · L²) to search · Space O(N · L²) for the buckets

Counter-questions on this approach

⭐ "Why is building the buckets O(N · L²) and not O(N · L)?"

Because each of the L patterns per word is a new string of length L — substring plus concatenation is O(L), and hashing it is another O(L).

So it's N words × L patterns × O(L) per pattern = O(N · L²). With N = 5000, L = 10 that's 5 × 10^5 — small, but worth stating precisely rather than hand-waving it to O(N · L).

⭐ "Why does BFS give the shortest path here but not in general?"

Because every edge has the same cost. BFS expands in order of edge count, so the first time it reaches a node, that's the fewest edges — no later route can improve it.

That breaks the moment edges have different weights: a two-edge path could be cheaper than a one-edge path. Then you need Dijkstra, whose priority queue orders by accumulated cost instead of hop count.

⭐ "Why visited.add(next) inside the if rather than a separate contains-then-add?"

Set.add returns false if the element was already present, so it tests and inserts in one hash operation. Two calls would hash twice.

More importantly it marks on enqueue, not dequeue. A word reachable from several words in the same level would otherwise be queued multiple times before being processed, inflating the queue and duplicating work.

⭐ "Why the early endWord check before any BFS?"

Because every intermediate word — including the final one — must be in wordList. If endWord isn't there, no valid sequence exists regardless of the graph, so it's an O(1) rejection before building anything.

That's the case most solutions miss, and it's cheap to handle.

"Why does level start at 1?"

Because the answer counts words, not transformations. hit → hot → dot → dog → cog is four changes but five words. Starting at 1 for beginWord and incrementing per level makes the returned value the word count directly.

"beginWord may not be in wordList. Does that matter?"

Not for correctness — it's the starting node whether or not it's listed, and its patterns are looked up against the buckets built from wordList. It just won't appear in any bucket itself, which is fine since nothing needs to reach it.

If beginWord is in the list, marking it visited up front stops the search returning to it.

"What's the space cost of the buckets?"

N · L pattern strings of length L, so O(N · L²) characters — 5 × 10^5 here. Acceptable, but it is the dominant memory cost, and at much larger N you'd consider generating neighbours by character substitution instead, trading time for space.

Approach 3 — Bidirectional BFS

Search from both ends simultaneously, always expanding the smaller frontier, and stop when they meet.

• Time roughly O(b^(d/2)) instead of O(b^d) · Space O(N · L²)

Counter-questions on this approach

⭐ "Why is searching from both ends faster?"

Because the frontier grows exponentially with depth. One search to depth d explores about b^d nodes; two searches to depth d/2 explore about 2 · b^(d/2), which is dramatically smaller.

With branching factor 10 and depth 6, that's 10^6 versus 2 × 10^3.

"Why expand the smaller frontier each round?"

To keep both sides balanced. If one side branches much more widely, expanding it repeatedly wastes the advantage — always growing the cheaper side keeps the total work near the b^(d/2) ideal.

"What's the termination condition?"

A word appearing in both frontiers. The answer is the sum of the two depths — and getting that arithmetic right is the fiddly part, since the meeting word is counted once, not twice.

"Would you write it in an interview?"

I'd mention it and write the single-directional version unless asked. It's a meaningful constant-factor win, but the bookkeeping — two frontiers, two visited sets, swap logic, and the meeting-point arithmetic — is easy to get wrong under pressure, and at N = 5000 the plain version is fast enough.

Comparison

4. Why the Optimal Wins

The BFS is optimal in both versions — it's the neighbour discovery that separates them.

Comparing every pair rediscovers the graph structure at every step, at O(N² · L). Wildcard buckets compute it once, and then a word's neighbours are L hash lookups. 2.5 × 10^8 → 5 × 10^5.

That's the real content of this problem: the traversal is standard, and the difficulty is representing the implicit graph cheaply.

The framing worth keeping:

Unweighted shortest path means BFS — the first arrival is optimal because every edge costs 1. But when the graph is implicit, building the adjacency can dominate the search, and wildcard bucketing turns an O(N²) pairwise comparison into O(N · L²) precomputation.

5. Java Prerequisites

Wildcard pattern generation

String pattern = w.substring(0, i) + '*' + w.substring(i + 1);

O(L) per pattern, so O(L²) per word. A char[] with one position swapped and restored avoids some allocation.

Set.add as test-and-insert

if (visited.add(next)) q.offer(next);      // false if already present

Level-by-level BFS — the snapshot idiom for counting depth:

int size = q.size();
for (int i = 0; i < size; i++) { ... }
level++;

computeIfAbsent for bucketing

buckets.computeIfAbsent(pattern, k -> new ArrayList<>()).add(w);

getOrDefault(pattern, List.of()) avoids a null check and allocates nothing on a miss.

6. Interview Communication Guide

Clarifying questions: Must endWord be in wordList (yes — and if it isn't, return 0 immediately)? Does beginWord need to be in the list (no)? Are all words the same length (yes)? Does the answer count words or transformations (words — so hit→hot→dot→dog→cog is 5)? Case sensitivity (lowercase only)?

The pitch

"Each word is a node, and two words are adjacent when they differ by exactly one letter. Every transformation costs the same, so the shortest sequence is the fewest edges — which means BFS. The first time BFS reaches endWord, that's the minimum, because BFS expands strictly in order of edge count.

The naive neighbour test is comparing each word against every other, which is O(N² · L) — about 2.5 × 10^8 at these limits. That dominates the BFS completely; the traversal visits at most 5000 nodes.

So the real work is building the adjacency cheaply. Two words differ by one letter exactly when they match a pattern with one position wildcarded — "hot" and "dot" both match "*ot". I bucket every word under its L patterns once, then a word's neighbours are just L hash lookups.

That's O(N · L²) — the squared L because each pattern is a new L-character string to build and hash. About 5 × 10^5, so roughly 500× better.

A few details. I check up front whether endWord is even in the list — every intermediate word must be, including the last, so if it's absent the answer is 0 with no work. I mark words visited on enqueue, not dequeue, so a word reachable from several words in the same level doesn't get queued repeatedly. And level starts at 1, because the answer counts words rather than transformations.

If asked to go further, bidirectional BFS searches from both ends and stops when the frontiers meet — roughly b^(d/2) instead of b^d. It's a real win, but the two-frontier bookkeeping and the meeting-point arithmetic are easy to get wrong, so I'd only write it if asked."

Edge cases to volunteer:

Name the missing-endWord case. It's an O(1) rejection that many solutions skip, and without it the BFS runs to exhaustion before returning 0 — correct but wasteful, and it's the first thing an interviewer checks.

7. Follow-Up Questions — Modified Constraints

⭐ "Return all shortest transformation sequences, not just the length."

LeetCode 126, and substantially harder. BFS to build a parent DAG — recording every predecessor at the previous level, not just one — then backtrack through it to enumerate all paths. The BFS is similar; the reconstruction is where the work is, and there can be exponentially many paths.

⭐ "What if transformations had different costs?"

BFS breaks, because the first arrival is no longer the cheapest. You'd need Dijkstra with a priority queue ordered by accumulated cost — O(E log V). This is the clearest statement of why BFS works here at all.

"Allow insertions and deletions as well as substitutions."

Words are no longer all the same length, so the wildcard bucketing needs extending — patterns for deletion ("hot" → "ot", "ht", "ho") as well as substitution. This is edit-distance-1 adjacency, and it's how spell-checkers build candidate sets.

"What if wordList had 10^6 words?"

The buckets become 10^6 × L pattern strings — a lot of memory. You'd generate neighbours on the fly by substituting each of 26 letters at each position, O(26L) per word, trading time for space. That's often the better choice at scale, and it's O(26 · L² ) per word rather than a precomputed map.

"Is the shortest path unique?"

Generally no — hit → hot → lot → log → cog is also length 5 in the example. The problem asks only for the length, which is why any shortest path suffices.

"How would you handle a wordList with duplicates?"

new HashSet<>(wordList) deduplicates automatically, and the buckets would otherwise hold repeats, causing redundant enqueue attempts that visited.add rejects anyway. Correct either way, but deduplicating up front avoids the wasted lookups.