4.20.13 — Word Ladder

LeetCode 127 · Hard · ★ Blind 75

The problem

Transform beginWord into endWord, changing one letter at a time, where every intermediate word must be in the given word list. Return the number of words in the shortest such sequence, or 0 if there is none.

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

hit → hot → dot → dog → cog       →  5   (the count includes both ends)

Words are up to 10 letters, and the list holds up to 5,000 words.

The pattern

This is a graph, even though nobody gave you one. Each word is a node, and two words are joined by an edge when they differ in exactly one letter.

The question is "the fewest steps", every step costs the same, so it is BFS — and only BFS. This is the clearest example in the book of a problem where the graph is implicit and the whole skill is recognising it.

Two things then have to be decided: how to find a word's neighbours, and how to avoid revisiting.

Finding neighbours cheaply

The obvious way is to compare the current word against every word in the list and keep those differing by one letter. That is O(N \times L) per word and O(N^2 \times L) overall — 25 million character comparisons here, and it is the version that times out.

The better way: generate the neighbours instead of searching for them.

For a word of length L, try replacing each position with each of the 26 letters. That gives 26L candidates, and a set lookup says which of them are real words. For L = 10 that is 260 lookups per word — independent of how many words exist.

O(N \times L \times 26) overall, and with N = 5000 and L = 10 that is about 1.3 million operations instead of 25 million. Generating candidates beats searching for matches whenever the alphabet is small and the dictionary is large, and that trade is the real lesson of this problem.

The solution

Python

from collections import deque

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        words = set(wordList)
        if endWord not in words:
            return 0                                  # unreachable by definition

        queue = deque([beginWord])
        words.discard(beginWord)
        steps = 1                                     # the count includes beginWord

        while queue:
            for _ in range(len(queue)):               # one level = one step
                word = queue.popleft()
                if word == endWord:
                    return steps

                for i in range(len(word)):
                    for ch in 'abcdefghijklmnopqrstuvwxyz':
                        candidate = word[:i] + ch + word[i+1:]
                        if candidate in words:
                            words.discard(candidate)  # mark visited ON ENQUEUE
                            queue.append(candidate)
            steps += 1

        return 0

TypeScript

function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  const words = new Set(wordList);
  if (!words.has(endWord)) return 0;

  let queue: string[] = [beginWord];
  words.delete(beginWord);
  let steps = 1;

  while (queue.length) {
    const next: string[] = [];
    for (const word of queue) {
      if (word === endWord) return steps;

      for (let i = 0; i < word.length; i++) {
        for (let c = 97; c < 123; c++) {
          const candidate = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
          if (words.has(candidate)) {
            words.delete(candidate);
            next.push(candidate);
          }
        }
      }
    }
    queue = next;
    steps++;
  }

  return 0;
}

Four details.

Removing a word from the set is the visited mark. No separate structure — a word that has been queued is deleted, so it can never be queued again. This is the same "the data structure is the visited set" idea as marking a grid in 4.20.1.

Delete on enqueue, not on dequeue. Several words in the same level may generate the same neighbour; deleting immediately stops it being queued several times.

steps starts at 1, because the problem counts both endpoints. hit → hot → dot → dog → cog is four transformations and five words.

The early check that endWord is in the list saves a full search of a graph that cannot contain the target.

Complexity

O(N \times L^2) — for each of the N words, you build 26L candidate strings, and each string costs O(L) to construct and hash. The 26 is a constant.

Space is O(N \times L) for the set and the queue.

Bidirectional BFS

The genuine optimisation, and worth naming even if you do not write it.

Search from both ends at once, alternating, and stop when the two frontiers meet.

A BFS frontier grows roughly like b^d for branching factor b and depth d. Two searches each of depth d/2 cost about 2 \times b^{d/2}, which is dramatically less than b^d. On a ladder of length 10 with a branching factor of 10, that is 200 nodes instead of 10 billion.

The implementation trick: keep two sets, and always expand the smaller one. That keeps both frontiers balanced and is where most of the practical gain comes from.

begin_set, end_set = {beginWord}, {endWord}
while begin_set and end_set:
    if len(begin_set) > len(end_set):
        begin_set, end_set = end_set, begin_set     # always expand the smaller
    next_set = set()
    for word in begin_set:
        for i in range(len(word)):
            for ch in 'abcdefghijklmnopqrstuvwxyz':
                candidate = word[:i] + ch + word[i+1:]
                if candidate in end_set:
                    return steps + 1                # the frontiers met
                if candidate in words:
                    words.discard(candidate)
                    next_set.add(candidate)
    begin_set = next_set
    steps += 1

Bidirectional search only works when you know the target, and when edges can be traversed in both directions. Both hold here.

The wildcard preprocessing alternative

Another way to find neighbours: build a map from patterns like "h*t" to the words matching them, in one pass. Then a word's neighbours are the union of the lists for its L patterns.

O(N \times L) to build, and each lookup is then cheap. It wins when the alphabet is large — the 26L candidate generation would become |\Sigma| \times L — and it costs more memory.

Naming both approaches and the condition that picks each is a strong answer.

Where this goes next

• Word Ladder II — return all shortest sequences. BFS to find the distances, then DFS backwards from the end using only edges that decrease the distance by one. Much harder, and the two-phase structure is the thing to remember.
• Open the Lock, Minimum Genetic Mutation, Jump Game III — all BFS over an implicit graph where neighbours are generated by a rule.
• Sliding Puzzle — the nodes are board states, and neighbours are the legal moves.

The recognition cue for the whole family: states, moves between them, and "the fewest moves". That is BFS over an implicit graph, and you never build the graph.

What the interviewer will push on

"Why BFS?" Fewest steps with equal-cost edges. DFS finds a path, not the shortest.

"How do you find neighbours?" Generate 26L candidates and test membership, rather than comparing against every word. Give both complexities.

"When do you mark a word visited?" On enqueue, by deleting it from the set.

"Why does steps start at 1?" Both endpoints are counted.

"How would you speed it up?" Bidirectional BFS, expanding the smaller frontier, with the 2b^{d/2} against b^d argument.

"What if you needed every shortest path?" Word Ladder II: BFS for distances, then DFS backwards along decreasing distances.

One thing to volunteer: say the modelling sentence first. "Each word is a node and an edge joins words differing by one letter, so this is a shortest path on an unweighted graph — BFS." Everything else follows, and the candidates who struggle here are the ones who never said it.

Next: 4.21 adds weights and the structures that go with them — Dijkstra, minimum spanning trees, and the union-find applications that show up as innocent-looking puzzles.