The problem
Mutate an 8-character gene (A/C/G/T) one character at a time; every intermediate must be in the gene bank. Return the minimum number of mutations from start to end, or −1.
Stuck? Reveal hints one at a time
How to approach it
- 1Put the bank in a set; if end is absent, return −1.
- 2BFS from the start gene at depth 0.
- 3Neighbors: substitute each of A/C/G/T at each of the 8 positions; keep those in the bank; remove on enqueue.
- 4Return depth when the end gene is dequeued; −1 otherwise.
Key insight
Recognizing isomorphic problems (this IS Word Ladder) lets you port a proven solution wholesale — pattern-matching over memorizing.
The solution
Watch out for
- Mutations count EDGES (unlike Word Ladder’s node count) — start at 0 here.
- The start gene may be outside the bank; the end gene must be inside.