DSA · Graph / BFS · #122
Minimum Genetic Mutation
Module 76 · difficulty 3/5·⏱ 30:00starts on first keystroke
A gene string is an 8-character sequence over the alphabet `{'A','C','G','T'}`. A **mutation** changes a single character to one of the other three. Given a `startGene`, an `endGene`, and a `bank` of valid gene strings, return the **minimum number of mutations** needed to transform `startGene` into `endGene`. Every intermediate gene along the path (after each single mutation) must appear in `bank`. The `endGene` itself must be in `bank` (unless it equals `startGene`). If no valid path exists, return `-1`. Implement `function minMutation(startGene, endGene, bank)` returning a number.
Examples
startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]→1— A single mutation at the last position; the result is in the bank.startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]→2— AACCGGTT -> AACCGGTA -> AAACGGTA, both intermediates valid.startGene = "AAAAACCC", endGene = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]→3
Constraints
- · startGene.length == endGene.length == 8
- · 0 <= bank.length <= 10
- · bank[i].length == 8
- · startGene, endGene, and bank[i] consist only of the characters 'A', 'C', 'G', 'T'
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.