Minimum Genetic Mutation

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:

  1. 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.

  2. Using BFS, initialize a queue with the start gene and set the minimum mutations to 0.

  3. Check the next gene in the queue against all valid mutations to see if it matches the target.

  4. If it matches the target, return the number of mutations required to reach it.

  5. If it does not match the target, add all valid mutations of the current gene to the queue.

  6. Remove the current gene from the queue.

  7. Increment the number of mutations required.

  8. Repeat steps 3 to 7 until the queue is empty.

  9. 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; 
    } 
}


Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]