Minimum Genetic Mutation
Medium · Graphs · Hash Table · String · Breadth-First Search
Problem
A gene is a string of 8 letters, each one of 'A', 'C', 'G' and 'T'. A mutation changes exactly one letter of a gene, for example "AACCGGTT" to "AACCGGTA".
Only some genes are valid: they are listed in bank, and every gene a sequence passes through after the start must be in it. The start gene itself does not have to be in the bank.
Return the fewest mutations that turn startGene into endGene, or -1 if it cannot be done. If the two are equal the answer is 0.
Examples
Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"] Output: 1
Change the last letter T to A; the result is in the bank.
Input: startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA", "AACCGCTA", "AAACGGTA"] Output: 2
"AACCGGTT" → "AACCGGTA" → "AAACGGTA".
Input: startGene = "AAAAACCC", endGene = "AACCCCCC", bank = ["AAAACCCC", "AAACCCCC"] Output: -1
The end gene is not in the bank, so no sequence may finish there.
Constraints
- startGene.length == endGene.length == bank[i].length == 8
- startGene, endGene and bank[i] use only A, C, G, T
- 0 <= len(bank) <= 1000
- bank holds distinct genes
Approaches
- Breadth-first search comparing with the bank — time O(N² · 8), space O(N)
Follow-up
Bidirectional search, growing one frontier from each end and stopping when they meet, explores far fewer genes on a large bank. The use cases count the shortest sequences and return the sequence itself.
Related problems
Start free on Cariara · Coding problems · System design studio
