Frontend Beauty
ESC

Type to search the knowledge base.

Word Ladder

Shortest transformation beginWord→endWord changing one letter — BFS on implicit word graph.

advanced3 min read
  • dsa
  • graph
  • interview
  • Google
  • Meta
  • Amazon
  • Microsoft

The problem

beginWord, endWord, and a word list. Each transform changes exactly one letter; intermediate words must be in the list. Return length of shortest transformation sequence (including begin), or 0 if impossible.

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

Brute force

DFS all paths, keep min length. Exponential; no good without heavy pruning.

Optimal: BFS for shortest path

Each word is a node; edges to words differing by one char. BFS from beginWord.

Naive neighbor gen: for each word, try all other words O(n). Better: for each position, try a–z mutations and set lookup.

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

  const q: string[] = [beginWord];
  const seen = new Set<string>([beginWord]);
  let steps = 1;

  while (q.length) {
    const size = q.length;
    for (let i = 0; i < size; i++) {
      const word = q.shift()!;
      if (word === endWord) return steps;

      const arr = word.split("");
      for (let p = 0; p < arr.length; p++) {
        const orig = arr[p];
        for (let c = 97; c <= 122; c++) {
          arr[p] = String.fromCharCode(c);
          const next = arr.join("");
          if (words.has(next) && !seen.has(next)) {
            seen.add(next);
            q.push(next);
          }
        }
        arr[p] = orig;
      }
    }
    steps++;
  }
  return 0;
}
Time O(n · L · 26) with set; n words length L
Space O(n · L)

Bidirectional BFS

Search from begin and end; when frontiers meet, path is found. Faster in practice on large lists — good follow-up.

Edge cases

  • endWord not in list → 0
  • beginWord == endWord — constraints usually differ
  • No path → 0
  • beginWord not required in list

Common bugs

  • Returning number of edges instead of words in sequence (off-by-one on steps)
  • Not freezing level size in BFS
  • Mutating word string incorrectly
  • DFS without level tracking claiming shortest

Interview delivery

  1. Shortest path → BFS.
  2. Implicit graph via mutations.
  3. Code level-order.
  4. Complexity.
  5. Bidirectional BFS flex.

Why BFS not DFS

Each edge has weight 1 (one letter change). BFS first time you reach endWord is shortest. DFS finds a path, not necessarily minimal, unless you explore all.

Neighbor generation cost

For word length L and dictionary size n:

  • Compare to all words: O(n·L) per node
  • Mutate each position × 26: O(L·26) set lookups

Mutation wins when n is large (thousands).

Begin word membership

Usually beginWord may or may not be in the list; you still start BFS from it. Ensure you don’t require it in the set. endWord must be in the list for a valid answer.

Further reading