Minimum Genetic Mutation

Medium#433states

A gene is a string of 8 letters, each A, C, G or T. One mutation changes one letter, and only genes from a given bank are allowed along the way; the start gene does not have to be in the bank. Find the fewest mutations from the start gene to the end gene, or -1 if it cannot be done. Our example: start AAGGTTCC, end AAGCTTCA, bank [AAGCTTCA, TAGGTTCC, AAGGTTCA] — the answer is 2.

433 Minimum Genetic MutationWalkthrough · 1×

Example: the fewest one-letter mutations from AAGGTTCC to AAGCTTCA through the bank [AAGCTTCA, TAGGTTCC, AAGGTTCA].

0 mutations1 mutation2 mutationsAAGGTTCCbankAAGCTTCATAGGTTCCAAGGTTCAqueuefront on the left—
not reachedwaiting in the queuecurrent genebank gene being checkeddone

The start AAGGTTCC is 0 mutations away

01/33
restart · back · play · step
Speed
1function minMutation(start, end, bank):
2 dist = {start: 0}
3 queue = [start]
4 while queue is not empty:
5 cur = queue.popFront()
6 if cur == end:
7 return dist[cur]
8 for gene in bank:
9 if gene not in dist and oneApart(cur, gene):
10 dist[gene] = dist[cur] + 1
11 queue.pushBack(gene)
12 return -1
state
dist
{AAGGTTCC: 0}
queue
–
cur
–
gene
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. A gene is a state and a mutation is an edge between bank genes one letter apart, so BFS reaches each gene first by the fewest mutations.
  2. The end gene being in the bank is not enough: two letters apart is two mutations, and the middle gene has to be in the bank too.
  3. Genes leave the queue fewest mutations first, so when the end gene leaves it, its distance is the answer; if the queue runs out first, there is no way and the answer is -1.

Complexity

Time O(b² · L) for a bank of b genes of length L: each gene is taken from the queue once and compared with the whole bank letter by letter. Memory O(b) for dist and the queue.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.