Minimum Genetic Mutation
Medium · Graphs · Explanation and code example
Breadth-First Search over Valid Genes
How it works
Each allowed one-character mutation is an unweighted edge between genes. Breadth-first search therefore reaches the target with the fewest changes. Generate candidates by changing each position to A, C, G, or T, and enqueue a bank gene only once.
Steps
- Reject a target absent from the bank.
- Explore all one-character candidates for each BFS level.
- Remove newly queued genes from the available bank and return the target level.
Complexity
- Time: O(b × a × g²) with string construction, for b bank genes, gene length g, and alphabet size a = 4; fixed g = 8 gives O(b).
- Space: O(bg) for the bank and queue.
Things to watch for
- Only genes in the bank are legal intermediate steps.
- Restore a changed position before trying the next position.
- Mark genes visited when enqueueing them.
Python code example
from functools import cache
import collections
class Solution:
def minMutation(self, startGene: str, endGene: str, bank: list[str]) -> int:
if startGene == endGene:
return 0
bankSet = set(bank)
if endGene not in bankSet:
return -1
GENES = 'ACGT'
q = collections.deque([startGene])
step = 1
while q:
for _ in range(len(q)):
wordList = list(q.popleft())
for j, cache in enumerate(wordList):
for c in GENES:
wordList[j] = c
word = ''.join(wordList)
if word == endGene:
return step
if word in bankSet:
bankSet.remove(word)
q.append(word)
wordList[j] = cache
step += 1
return -1
C++ code example
class Solution {
public:
int minMutation(string startGene, string endGene, vector<string>& bank) {
if (startGene == endGene) return 0;
unordered_set<string> bankSet{bank.begin(), bank.end()};
if (!bankSet.contains(endGene))
return -1;
constexpr string_view kGenes = "ACGT";
queue<string> q{{startGene}};
for (int step = 1; !q.empty(); ++step)
for (int sz = q.size(); sz > 0; --sz) {
string word = q.front();
q.pop();
for (int j = 0; j < word.length(); ++j) {
const char cache = word[j];
for (const char c : kGenes) {
word[j] = c;
if (word == endGene)
return step;
if (bankSet.contains(word)) {
bankSet.erase(word);
q.push(word);
}
}
word[j] = cache;
}
}
return -1;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.