Minimum Genetic Mutation
01 · Problem
A gene is an 8-character string made only of the letters 'A', 'C', 'G' and 'T'. A mutation changes exactly one character of a gene into another of these letters.
You are given a startGene, a target endGene, and a list bank of valid genes. Every gene produced by a mutation (including endGene itself) must appear in bank to count as a legal step. startGene is always considered valid, even if it is not in bank.
Return the minimum number of mutations needed to turn startGene into endGene. If startGene already equals endGene, return 0. If it cannot be done, return -1.
02 · Examples
startGene = "GATTACAG", endGene = "GATTACAT", bank = ["GATTACAT"]
1
Changing the last character from 'G' to 'T' produces endGene, which is in the bank, so one mutation suffices.
startGene = "CCGGTTAA", endGene = "CCGATTAC", bank = ["CCGGTTAC","CCGGTAAC","CCGATTAC"]
2
CCGGTTAA -> CCGGTTAC -> CCGATTAC. Each step changes one character and lands on a bank gene.
startGene = "AAAAAAAA", endGene = "CCCCCCCC", bank = ["AAAACCCC","CCCCCCCC"]
-1
No bank gene is exactly one character away from AAAAAAAA, so endGene cannot be reached.
03 · Constraints
- 01startGene.length == endGene.length == bank[i].length == 8
- 020 <= bank.length <= 10
- 03startGene, endGene and bank[i] contain only the characters 'A', 'C', 'G' and 'T'
- 04bank may contain duplicate genes; duplicates have no extra effect
04 · Optimal complexity
- Time
- O(n * L^2 * 4)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.