Sponsored
Sponsored
In this approach, we utilize the Breadth-First Search algorithm to explore the mutation process. The problem can be transformed into finding the shortest path in an unweighted graph (where nodes are gene strings and edges represent valid transformations as per the gene bank).
Steps involved:
startGene.endGene is reached, return the mutation count.endGene, return -1.Time Complexity: O(N * M * 4) where N is the number of steps in bank, M is length of startGene (8), and 4 is from trying each nucleotide.
Space Complexity: O(N) for the queue.
1using System;
2using System.Collections.Generic;
3
4public class GeneticMutation {
5 public int MinMutation(string startGene, string endGene, string[] bank) {
6 var geneBank = new HashSet<string>(bank);
7 if (!geneBank.Contains(endGene)) return -1;
8
9 var choices = new char[] {'A', 'C', 'G', 'T'};
10 var queue = new Queue<(string gene, int steps)>();
11 queue.Enqueue((startGene, 0));
12
13 while (queue.Count > 0) {
var (gene, steps) = queue.Dequeue();
if (gene == endGene) return steps;
for (int i = 0; i < gene.Length; i++) {
var geneArray = gene.ToCharArray();
char original = gene[i];
foreach (var choice in choices) {
if (choice == original) continue;
geneArray[i] = choice;
string newGene = new string(geneArray);
if (geneBank.Contains(newGene)) {
geneBank.Remove(newGene);
queue.Enqueue((newGene, steps + 1));
}
}
geneArray[i] = original;
}
}
return -1;
}
public static void Main() {
var gm = new GeneticMutation();
string startGene = "AACCGGTT";
string endGene = "AAACGGTA";
string[] bank = {"AACCGGTA", "AACCGCTA", "AAACGGTA"};
Console.WriteLine(gm.MinMutation(startGene, endGene, bank));
}
}The C# code solution uses a BFS implemented with a queue. It checks mutations by iterating over gene positions and attempting character replacements, using a set for quick lookup.
This approach aims to optimize the BFS by conducting simultaneous searches from both the start and end genes. This reduces the search space effectively.
Steps:
startGene and endGene, respectively.Time Complexity: O(N * M * 4), with quicker terminations due to bidirectional checks.
Space Complexity: O(N) for two sets tracking forward and backward layers.
1class Solution:
2
The Python implementation of bidirectional BFS harnesses two sets to represent forward and backward search layers, refining the mutation search space substantially.