352. Minimum Genetic Mutation
A gene is a string of exactly 8 characters drawn from 'A', 'C', 'G', 'T'. A mutation replaces one single character of a gene with a different letter — and a mutation is only valid if the string it produces appears in a given gene bank.
You receive three things: a string startGene, a string endGene (the target), and bank, a list of valid gene strings. Return the smallest number of valid mutations that turns startGene into endGene, or -1 if no sequence of valid mutations gets there. The start gene itself does not need to appear in the bank, but every gene you mutate into — including the target — must.
Example 1:
Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1
Explanation: Changing the last character T → A produces the target directly, and that string is in the bank, so one mutation suffices.
Example 2:
Input: startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA", "AACCGCTA", "AAACGGTA"]
Output: 2
Explanation: AACCGGTT → AACCGGTA → AAACGGTA uses two single-character changes, and every intermediate string is in the bank. No single mutation reaches the target, so 2 is minimal.
Constraints:
- startGene.length == endGene.length == 8
- 0 ≤ bank.length ≤ 10
- Every gene consists only of the characters 'A', 'C', 'G', 'T'.
Hints:
Model it as a graph: every gene string is a node, and two genes share an edge when they differ in exactly one position. The question becomes: what is the length of the shortest path from the start gene to the target?
Shortest path over unit-weight edges is breadth-first search. Explore everything reachable in 1 mutation, then 2, and so on — the first time the target comes off the queue, its depth is the answer.
Mark a gene as visited when you enqueue it, not when you pop it; otherwise the same gene enters the queue many times.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
Expected output: 1