Transform a begin word into an end word, changing one letter at a time. Every intermediate word must be in the word list. Return the number of words in the shortest such sequence, or 0 if none exists.
DSA Animator › DSA Revision › Graph › Word Ladder
Remember: shortest path in an unweighted graph means BFS. Generate neighbours on the fly instead of building the graph. The video solves Word Ladder (LeetCode 127, Hard) with the BFS on Implicit Graph pattern from the Graph topic, and you can replay every step in the interactive Word Ladder animation.
Transform a begin word into an end word, changing one letter at a time. Every intermediate word must be in the word list. Return the number of words in the shortest such sequence, or 0 if none exists.
From hit to cog, with the list hot, dot, dog, lot, log, cog, the answer is 5. One shortest sequence is hit, hot, dot, dog, cog.
Exploring every possible sequence with depth first search can wander down long paths. The shortest sequence in an unweighted graph is exactly what breadth first search finds.
Think of every word as a node, with an edge between words that differ in one letter. We never build this graph completely. Instead, for the current word, try changing each position to every letter from a to z. Any result that is in the word set and not yet visited is a neighbour. Run BFS level by level, and the level where the end word appears is the answer.
Level 1 is hit. Changing the middle letter gives hot, which is level 2. From hot, we reach dot and lot, which are level 3. From dot we reach dog, and from lot we reach log, which are level 4. From dog, changing the first letter gives cog, at level 5. So the shortest sequence has 5 words.
In code, put the word list into a hash set. Start a queue with the begin word at level 1. For each word polled, try all positions and all 26 letters, and enqueue new words found in the set, removing them from the set. Return the level when the end word is reached, otherwise 0. It's O of the number of words times the word length times 26.
Remember: shortest path in an unweighted graph means BFS. Generate neighbours on the fly instead of building the graph.