Dare2Solve
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.
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.
bank
list into a set for O(1) lookup times.startGene
.endGene
is found, return the number of mutations.endGene
, return -1.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).
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.
class Solution {
public:
int minMutation(string startGene, string endGene, vector<string>& bank) {
unordered_set<string> bankSet(bank.begin(), bank.end());
queue<string> 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;
}
};
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
class Solution {
public int minMutation(String startGene, String endGene, String[] bank) {
Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
Queue<String> 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<String> 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;
}
}
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;
};