Why it works
- A gene is a state and a mutation is an edge between bank genes one letter apart, so BFS reaches each gene first by the fewest mutations.
- The end gene being in the bank is not enough: two letters apart is two mutations, and the middle gene has to be in the bank too.
- Genes leave the queue fewest mutations first, so when the end gene leaves it, its distance is the answer; if the queue runs out first, there is no way and the answer is -1.
Complexity
Time O(b² · L) for a bank of b genes of length L: each gene is taken from the queue once and compared with the whole bank letter by letter. Memory O(b) for dist and the queue.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗