HardGraphBFSHash Set·AmazonFacebook⚡ Very Frequent
A transformation sequence from beginWord to endWord uses words from wordList where each step changes exactly one letter and each intermediate word must be in the list. Return the number of words in the shortest transformation sequence, or 0 if no sequence exists.
1 ≤ beginWord.length ≤ 10
1 ≤ wordList.length ≤ 5000
Example
beginWord"hit"
endWord"cog"
wordList["hot","dot","dog","lot","log","cog"]
Output5
hit → hot → dot → dog → cog
Real-world analogy: Word association game
🎯 Word chain game: You're playing a word game where you must reach a target word by changing one letter at a time, and every intermediate word must be valid. Think of it like a map where words are cities and roads connect words that differ by one letter.
Why BFS is optimal: You want the shortest path. BFS explores words level by level — level 1 is all words 1 step from the start, level 2 is all words 2 steps away, etc. The moment you reach the target, you know it's the shortest path. DFS would find a path but not necessarily the shortest.
The trick: Instead of pre-computing all word pairs (O(N²·L)), try every possible single-letter substitution (26 per position per word) and check if it's in the wordSet. This makes neighbor-finding O(26·L) per word.
Algorithm — BFS
1. Add all wordList words to a set. If endWord not in set → return 0. 2. BFS: queue starts with (beginWord, level=1). 3. For each dequeued word: If word == endWord → return level Try all 26-letter substitutions at each position If new word is in wordSet and not visited → enqueue 4. If queue empties → return 0
Approach
Time
Space
Notes
BFS ✓
O(N·L·26)
O(N·L)
N=words, L=word length
Bidirectional BFS
O(N·L·√26)
O(N·L)
Search from both ends, meet in middle
Visualizer — BFS Word Traversal
■ Amber = begin · ■ Indigo = in queue / neighbors · ■ Green = visited or found · ■ Red = unreachable
The endWord must be in the word list. Forgetting this check means the BFS runs to completion without ever finding the target, returning 0 when it should be fast.
Not marking visited when enqueuing
Mark a word as visited when you enqueue it, not when you dequeue it. Otherwise the same word gets added to the queue multiple times from different neighbors, exponentially blowing up the queue.
Using O(N²) neighbor pre-computation
Don't pre-compute all pairs of words that differ by one letter — that's O(N²·L). Instead, generate all 26-letter variations of the current word and check if each is in the wordSet. O(26·L) per word, no pre-computation needed.
Pattern: Implicit graph BFS
The "graph" is implicit — edges are words differing by 1 letter, computed on-the-fly.
BFS guarantees shortest path. DFS finds a path but not necessarily shortest.
Mark visited on enqueue, not dequeue, to prevent duplicate processing.
Discussion
…