Solution For Minimum Genetic Mutation
The Minimum Genetic Mutation is a problem on LeetCode that requires finding the minimum number of mutations needed to reach the target gene from the start gene, given a list of valid gene mutations.
Solution to Minimum Genetic Mutation Problem:
The problem asks for the minimum number of mutations needed to reach the target gene from the start gene.
The solution involves using BFS (Breadth First Search) algorithm to search through all possible valid mutations and return the minimum steps required to reach the target gene from the start gene.
Algorithm:
Create a set of valid mutations.
This will reduce the time complexity when checking if a new mutation is valid by performing a hash lookup.Using BFS, initialize a queue with the start gene and set the minimum mutations to 0.
Check the next gene in the queue against all valid mutations to see if it matches the target.
If it matches the target, return the number of mutations required to reach it.
If it does not match the target, add all valid mutations of the current gene to the queue.
Remove the current gene from the queue.
Increment the number of mutations required.
Repeat steps 3 to 7 until the queue is empty.
If the target is not found, return -1.
Coding the Solution:
“`
from collections import deque
class Solution:
def minMutation(self, start: str, end: str, bank: List[str]) -> int:
“””
:type start: str
:type end: str
:type bank: List[str]
:rtype: int
“””
# Create a set of valid mutations
valid_mutations = set(bank)
# Check if the end gene is not valid
if end not in valid_mutations:
return -1
# Initialize the queue with the start gene and minimum mutations
queue = deque([(start, 0)])
# BFS
while queue:
# Get the current gene and minimum mutations
curr_gene, curr_mutations = queue.popleft()
# Check if the current gene matches the target gene
if curr_gene == end:
return curr_mutations
# Find all valid mutations of the current gene
for i in range(len(curr_gene)):
for char in ["A", "C", "G", "T"]:
mutant_gene = curr_gene[:i] + char + curr_gene[i+1:]
# If the mutation is valid, add it to the queue
if mutant_gene in valid_mutations:
valid_mutations.remove(mutant_gene)
queue.append((mutant_gene, curr_mutations+1))
# Target gene not found
return -1
“`
The time complexity of the solution is O(N^2*L), where N is the length of the bank and L is the length of the gene.
Step by Step Implementation For Minimum Genetic Mutation
A gene string can be represented by an 8-character long string, with choices from "A", "C", "G", "T". Suppose we need to investigate about a mutation (mutation from "start" to "end"), where ONE mutation is defined as ONE single character changed in the gene string. For example, "AACCGGTT" -> "AACCGGTA" is 1 mutation. Also, there is a given gene "bank", which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string. Now, given 3 things - start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from "start" to "end". If there is no such a mutation, return -1. Note: Starting point is assumed to be valid, so it might not be included in the bank. If multiple mutations are needed, all mutations during in the sequence must be valid. You may assume start and end string is not the same. Example 1: start: "AACCGGTT" end: "AACCGGTA" bank: ["AACCGGTA"] return: 1 Example 2: start: "AACCGGTT" end: "AAACGGTA" bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"] return: 2 Example 3: start: "AAAAACCC" end: "AACCCCCC" bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"] return: 3
A gene string can be represented by an 8-character long string, with choices from "A", "C", "G", "T". Suppose we need to investigate about a mutation (mutation from "start" to "end"), where ONE mutation is defined as ONE single character changed in the gene string. For example, "AACCGGTT" -> "AACCGGTA" is 1 mutation. Also, there is a given gene "bank", which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string. Now, given 3 things - start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from "start" to "end". If there is no such a mutation, return -1. Note: Starting point is assumed to be valid, so it might not be included in the bank. If multiple mutations are needed, all mutations during in the sequence must be valid. You may assume start and end string is not the same. Example 1: start: "AACCGGTT" end: "AACCGGTA" bank: ["AACCGGTA"] return: 1 Example 2: start: "AACCGGTT" end: "AAACGGTA" bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"] return: 2 Example 3: start: "AAAAACCC" end: "AACCCCCC" bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"] return: 3
There are many possible solutions for this problem. One potential solution is as follows: 1. Create a function that takes in an array of strings representing the gene sequence and a string representing the target gene sequence. 2. Use a for loop to iterate through the array of strings. 3. For each string in the array, use another for loop to iterate through the characters in the string. 4. If the character at the current index is not equal to the character at the same index in the target gene sequence, then increment a counter variable. 5. After the nested for loop has finished, if the counter variable is less than the current minimum, then update the minimum to be the counter variable. 6. After the outer for loop has finished, return the minimum.
One possible solution to the leetcode problem minimum-genetic-mutation is as follows: int minMutation(string start, string end, vector& bank) { //create a queue for storing the strings that need to be checked queue toCheck; //create a set for storing the strings that have been checked set checked; //create a variable for storing the minimum number of mutations int min = 0; //push the starting string into the queue toCheck.push(start); //while the queue is not empty while(!toCheck.empty()){ //get the size of the queue int size = toCheck.size(); //for each string in the queue for(int i = 0; i < size; i++){ //get the next string in the queue string current = toCheck.front(); toCheck.pop(); //if the current string is the end string, return the minimum number of mutations if(current == end) return min; //for each string in the bank for(string s : bank){ //if the current string is not the same as the string in the bank and //if the current string has not been checked yet if(current != s && checked.find(s) == checked.end()){ //count the number of mutations between the current string and the string in the bank int mutations = 0; for(int j = 0; j < 8; j++){ if(current[j] != s[j]) mutations++; } //if the number of mutations is 1 if(mutations == 1){ //push the string in the bank into the queue toCheck.push(s); //add the string in the bank to the set of checked strings checked.insert(s); } } } } //increment the minimum number of mutations min++; } //if we reach this point, it means that there is no solution return -1; }
public class Solution {
public int MinMutation(string start, string end, string[] bank) {
// create a set to store all strings in the bank
// for quick lookup
HashSet bankSet = new HashSet(bank);
// keep track of the strings we've seen so far in our
// search so that we don't process them again
HashSet seen = new HashSet();
// create a queue to store the strings we need to process
// in our search
Queue queue = new Queue();
// enqueue the starting string
queue.Enqueue(start);
// keep track of the number of mutations needed
int numMutations = 0;
// while there are still strings to process in the queue
while (queue.Count > 0) {
// get the next string to process from the queue
string current = queue.Dequeue();
// if we've seen this string before, skip it
if (seen.Contains(current)) {
continue;
}
// if this is the ending string, we're done!
if (current == end) {
return numMutations;
}
// mark this string as seen
seen.Add(current);
// loop through each character in the string
for (int i = 0; i < current.Length; i++) {
// create a temporary character array that we can
// use to modify the characters in the string
char[] chars = current.ToCharArray();
// loop through each character A, C, G, and T
for (char c = 'A'; c <= 'T'; c++) {
// if this character is the same as the character
// we're currently processing, skip it
if (chars[i] == c) {
continue;
}
// change the character at the current position
// in the string to the new character
chars[i] = c;
// create a new string from the character array
string newString = new string(chars);
// if the new string is in the bank, add it to the queue
if (bankSet.Contains(newString)) {
queue.Enqueue(newString);
}
}
}
// since we only processed one string in the queue,
// we can increment the mutation count
numMutations++;
}
// if we reach here, it means that we never found the end string
// which means there is no way to mutate from the start string
// to the end string
return -1;
}
}