The word ladder
A word ladder asks for the fewest single letter changes to turn one word into another, where every intermediate word must be valid. Turning cold into warm might go cold, cord, card, ward, warm. The goal is the shortest such chain.
Words as a graph
Model each valid word as a vertex. Connect two words with an edge when they differ by exactly one letter. The shortest ladder is then the shortest path in this graph, so BFS is the right tool because all edges count equally.
- Start BFS from the begin word.
- For the current word, generate every neighbor that differs by one letter and exists in the dictionary.
- The first time you reach the target word, the BFS layer number is the answer.
Generating neighbors efficiently
Comparing the current word to every dictionary word is slow. A faster trick groups words by wildcard patterns, replacing one position with a blank. Words sharing a pattern differ by that single letter, so the pattern acts as a bucket of neighbors. Bidirectional BFS from both ends can shrink the search further.
Key idea
Treat words as vertices joined when they differ by one letter, then BFS gives the shortest valid transformation chain.