
Description
The goal is to determine the minimum number of mutations required to transform a startGene
into an endGene
using a set of allowed mutations provided in the bank
. Each mutation involves changing a single character in the gene string. If the transformation is not possible, return -1.
Intuition
The problem can be approached using Breadth-First Search (BFS) because it involves finding the shortest path (minimum mutations) in an unweighted graph where each gene is a node and edges exist between nodes that can be reached by a single mutation.
Approach
- Convert the
bank
list into a set for O(1) lookup times. - Use a queue to implement BFS, starting with the
startGene
. - Track the number of mutations required.
- For each gene in the queue, generate all possible single mutations.
- If a mutated gene is in the bank, add it to the queue and remove it from the bank.
- If the
endGene
is found, return the number of mutations. - If the queue is exhausted without finding the
endGene
, return -1.
Complexity
Time Complexity:
O(N * L^2), where N is the number of genes in the bank and L is the length of each gene. For each gene, we generate all possible mutations (L) and check if they are in the bank (L).
Space Complexity:
O(N * L), where N is the number of genes and L is the length of each gene. The space is used for the queue and the bank set.
Code
C++
class Solution {
public:
int minMutation(string startGene, string endGene, vector& bank) {
unordered_set bankSet(bank.begin(), bank.end());
queue q;
q.push(startGene);
int ans = 1;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; ++i) {
string gene = q.front();
q.pop();
for (auto it = bankSet.begin(); it != bankSet.end(); ) {
string b = *it;
int diff = 0;
for (int j = 0; j < 8 && diff < 2; ++j) {
diff += (gene[j] == b[j]) ? 0 : 1;
}
if (diff == 1) {
if (b == endGene) {
return ans;
}
q.push(b);
it = bankSet.erase(it);
} else {
++it;
}
}
}
++ans;
}
return -1;
}
};
Python
class Solution:
def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
bankSet = set(bank)
if endGene not in bankSet:
return -1
queue = deque([startGene])
mutations = 0
while queue:
for _ in range(len(queue)):
gene = queue.popleft()
if gene == endGene:
return mutations
for i in range(len(gene)):
for c in "ACGT":
mutated = gene[:i] + c + gene[i+1:]
if mutated in bankSet:
queue.append(mutated)
bankSet.remove(mutated)
mutations += 1
return -1
Java
class Solution {
public int minMutation(String startGene, String endGene, String[] bank) {
Set bankSet = new HashSet<>(Arrays.asList(bank));
Queue q = new LinkedList<>();
q.offer(startGene);
int ans = 1;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
String gene = q.poll();
Iterator it = bankSet.iterator();
while (it.hasNext()) {
String b = it.next();
int diff = 0;
for (int j = 0; j < 8 && diff < 2; j++) {
if (gene.charAt(j) != b.charAt(j)) {
diff++;
}
}
if (diff == 1) {
if (b.equals(endGene)) {
return ans;
}
q.offer(b);
it.remove();
}
}
}
ans++;
}
return -1;
}
}
JavaScript
var minMutation = function(startGene, endGene, bank) {
const bankSet = new Set(bank);
let q = [startGene];
let ans = 1;
while (q.length > 0) {
let nextQ = [];
for (const gene of q) {
for (const b of bankSet.values()) {
let diff = 0;
for (let i = 0; i < 8 && diff < 2; i++) {
diff += gene[i] === b[i] ? 0 : 1;
}
if (diff === 1) {
if (b === endGene) {
return ans;
}
nextQ.push(b);
bankSet.delete(b);
}
}
}
ans++;
q = nextQ;
}
return -1;
};