Word Ladder
Given a start word, an end word and a dictionary of equal-length words, find the length of the shortest transformation sequence from start to end where each step changes exactly one letter and every intermediate word is in the dictionary. Return 0 if impossible.
- 1 ≤ word length ≤ 10
- 1 ≤ wordList.length ≤ 5000
- Lowercase letters, all words distinct
- Shortest sequence of transformations
- Every step has the same cost — unweighted graph
- Neighbours are generated by substituting one letter
BFS explores in rings of increasing distance, so the first time it reaches a node it has found a shortest path in terms of edge count. "Minimum number of moves" on any state space where each move costs 1 is BFS, whether the states are grid cells, words, or puzzle configurations.
Treat words as nodes with an edge between words differing in one letter. Run BFS from the start word: for each dequeued word, generate all L · 26 one-letter variants, and for each variant present in the dictionary set, remove it from the set (marking visited) and enqueue it with depth + 1. The first time the end word is generated, its depth is the answer. BFS finds the shortest path because all edges cost one.
- Bidirectional BFS from both ends dramatically shrinks the frontier. Precomputing wildcard patterns like
h*tas adjacency buckets avoids the 26-letter loop.