Word Ladder

Start from brute force

The obvious approach builds the graph explicitly: compare every pair of words, letter by letter, and add an edge whenever they differ in exactly one position; then run BFS from begin. It is correct, because BFS on that graph finds the shortest ladder. But the comparisons cost O(N² · L) for N words of length L, and a dense graph needs O(N²) space for its edges. At 5,000 words that is about 12.5 million pairs before the search even starts, almost all of them answering “no”. Enumerating every path with DFS and keeping the shortest is worse still: the number of paths can grow exponentially with the length of the ladder.

The approach

Treat each word as a node and each one-letter change as an edge, but never build the graph: generate a word's neighbors only when BFS reaches it. BFS explores in order of distance, so the first time end comes out of the queue, the depth stored with it is the shortest ladder. The invariant: every word in the queue was reached by a shortest path, and each word enters the queue at most once.

The reference puts words into wordset for constant-time lookups and returns 0 at once if end is not in it. The queue holds (word, depth) pairs, starting with (begin, 1) because the answer counts words, not steps. For each dequeued word, it tries every position i and every letter c, building nxt = word[:i] + c + word[i + 1:]; a candidate that is in wordset and not yet in seen is marked seen immediately and enqueued with depth + 1. Marking at enqueue time, not at dequeue time, is what keeps a word from being queued twice by two words on the same level.

Walk through an example

Trace the first example, ladder_length("hit", "cog", ["hot","dot","dog","lot","log","cog"]), one dequeue per row.

Complexity

Optimal: O(N · 26 · L²) time, because at most N words are dequeued, each generates 26 · L candidates, and building and hashing a candidate costs O(L); O(N · L) space for wordset, seen and the queue. Brute force (pairwise graph, then BFS): O(N² · L) time and up to O(N²) space.

Edge cases to test

• end not in the list: ladder_length("hit", "cog", ["hot","dot","dog","lot","log"]) → 0, returned before any search.
• end in the list but unreachable: ladder_length("hit", "cog", ["hot", "cog"]) → 0, because hot and cog differ in two letters and the queue runs dry.
• One step: ladder_length("a", "c", ["b", "c"]) → 2. The answer counts words, so a single change is 2, not 1.
• begin equal to end: ladder_length("hit", "hit", ["hit"]) → 1, but with an empty list it returns 0, because the membership check on end runs first.
• Words of other lengths in the list, such as hitt or co, are never generated as candidates, so they are ignored without any special case.
• Letters outside a to z: the loop only tries lowercase letters, so ladder_length("hit", "hOt", ["hOt"]) → 0. That is why the constraints require lowercase words.

Common mistakes

• Using DFS — it explores deep first and does not give the shortest ladder; BFS does.
• Comparing every pair of words (O(N²·L)) instead of generating each word’s neighbors on demand or grouping words by wildcard patterns.
• Not marking words visited, so BFS revisits and can loop.
• Counting steps instead of words: starting the depth at 0 gives 4 for the first example instead of 5.

Follow-ups an interviewer asks next

How would bidirectional BFS speed this up?

Run two searches, one from begin and one from end, and always expand the smaller frontier by one level; stop when a newly generated word is already in the other side’s visited set. If each word has about b neighbors and the ladder has d steps, a one-sided search explores on the order of b^d words, while two halves explore about 2 · b^(d/2).

How would you return the actual ladders (Word Ladder II)?

Record parents during the BFS. For one shortest ladder, store the first parent of each word and walk back from end. For all of them, process level by level and mark words visited only after the whole level finishes, so every same-level parent is kept, then enumerate paths backward. The number of shortest ladders can grow exponentially, so the output itself can be the bottleneck.

When are wildcard buckets better than trying 26 letters?

Precompute a map from patterns like h*t to the words matching them; a word’s neighbors are then the union of its L buckets. That costs O(N · L²) to build and avoids generating 26 candidates per position, which pays off when the alphabet is large, such as Unicode text, or when most letter substitutions are not words.

What if some letter changes cost more than others?

Then the graph is weighted and BFS no longer finds the cheapest ladder: use Dijkstra’s algorithm with a priority queue keyed by cost. If every change costs at least 1, A* with the number of differing letters as the heuristic is admissible, because each step fixes at most one letter.

Where this shows up

Word ladder is BFS-for-shortest-path on a graph you generate on the fly — the same “fewest steps between states” pattern as puzzle solvers, refactor/transformation planners, and any unweighted shortest-path problem where you expand neighbors lazily rather than storing the whole graph.

Reference solution

from collections import deque

def ladder_length(begin, end, words):
    wordset = set(words)
    if end not in wordset:
        return 0                       # unreachable by definition

    queue = deque([(begin, 1)])        # (word, words-used-so-far)
    seen = {begin}
    while queue:
        word, depth = queue.popleft()
        if word == end:
            return depth
        for i in range(len(word)):     # try changing each position
            for c in "abcdefghijklmnopqrstuvwxyz":
                nxt = word[:i] + c + word[i + 1:]
                if nxt in wordset and nxt not in seen:
                    seen.add(nxt)
                    queue.append((nxt, depth + 1))
    return 0


print(ladder_length("hit", "cog", ["hot","dot","dog","lot","log","cog"]))  # -> 5
print(ladder_length("hit", "cog", ["hot","dot","dog","lot","log"]))        # -> 0

function ladderLength(begin: string, end: string, words: string[]): number {
  const wordset = new Set(words);
  if (!wordset.has(end)) return 0;              // unreachable

  const queue: [string, number][] = [[begin, 1]];
  const seen = new Set([begin]);
  const alphabet = "abcdefghijklmnopqrstuvwxyz";
  while (queue.length) {
    const [word, depth] = queue.shift()!;
    if (word === end) return depth;
    for (let i = 0; i < word.length; i++) {     // change each position
      for (const c of alphabet) {
        const nxt = word.slice(0, i) + c + word.slice(i + 1);
        if (wordset.has(nxt) && !seen.has(nxt)) {
          seen.add(nxt);
          queue.push([nxt, depth + 1]);
        }
      }
    }
  }
  return 0;
}

console.log(ladderLength("hit", "cog", ["hot","dot","dog","lot","log","cog"])); // -> 5
console.log(ladderLength("hit", "cog", ["hot","dot","dog","lot","log"]));       // -> 0