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)