Word Ladder

Difficulty: Hard

Problem

Transform beginWord into endWord by changing ONE letter at a time, where every intermediate word must exist in the given wordList. Return the number of words in the SHORTEST such transformation sequence (including both endpoints), or 0 if impossible. The final boss of this track, because the graph is invisible until you see it.

Example

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: hit → hot → dot → dog → cog is a shortest ladder: 5 words. (hit → hot → lot → log → cog also works.)

Brute-force approach

No brute-force phase: recognizing the hidden graph and applying BFS IS the lesson.

Optimal approach

Key insight: The word 'shortest' hands you the algorithm. The only real work is seeing words as nodes, then it's the same BFS you've run five times, with neighbors generated on the fly.

BFS over the implicit word graph: each dequeued word spawns its one-letter variants; dictionary hits are discovered neighbors. First arrival at endWord is the shortest ladder.

Steps

  1. If endWord isn't in the word set, return 0
  2. Queue holds (word, ladderLength), starting with (beginWord, 1)
  3. For each dequeued word: generate all 26×L one-letter variants
  4. Variants found in the set are neighbors: delete them (visited) and enqueue with length+1
  5. The first dequeue of endWord returns its ladder length; a drained queue returns 0

Time complexity: O(N × L²) where N = dictionary size, L = word length · Space complexity: O(N × L)