TLDR

1. Welcome!

2. Facts. Without motives.

3. Recommendations I live by!

4. Self-Gaslight of the week

5. JOBS & SCHOLARSHIPS

Day 5 : 433. Minimum Genetic Mutation

The task is to find the minimum number of mutations required to transform a start gene string into an end gene string, where each mutation changes one character, and all intermediate gene strings must be valid according to a given gene bank. 


If the transformation is not possible, the function should return -1.

Before we dive in,

Breathe.

Let’s analyze the problem a bit, and note, how the problem does not give us an adjacency matrix!! It gives us an array of strings ☹️ 

But there is a little trick that I am about to teach you….

Everything can become a graph!!!

Each word in the word bank can be considered a node, and the mutations between them can be considered edges.

To form our adjacency matrix we must iterate all possible gene strings in the bank. Two genes will be connected by an edge if they differ by one character.

To form the adjacency matrix we are going to:

1. Iterate over each Gene in the gene bank : For each gene in the gene in the bank, we’ll try to mutate character by character.

2. Generate all possible mutations: Replace each character in the gene string with one of the four possible characters : ('A', 'C', 'G', 'T')

3. Check if the mutation is valid: If the newly generated mutation exists in the gene bank and isn’t the same as the original gene (i.e., we haven’t mutated it to itself), it’s a valid mutation.

4. Add valid mutations to the adjacency matrix: Once a valid mutation is found, it represents an edge between the original gene and the mutated one in the graph. We add this edge to our adjacency list, representing our adjacency matrix.

***Since the problem assumes that startGene might not be included in the gene bank If a mutated version of the current gene matches the, that’s where the real mutation begins. We treat this mutated gene as our real starting point. ****

Now that we have our adjacency matrix we can begin!!

Since the problem specifically asks for the minimum number of mutations (or distance between the start and end genes), we will use Breadth-First Search (BFS).

REMEMBER IF THE PROBLEM ASKS FOR DISTANCE, IT IS ALWAYS BFS!!!

When calculating distances in a problem, we will have a distance list instead of a visited list. We maintain a distance dictionary that tracks the number of mutations it takes to reach each gene. Initially, the startGene is set to a distance of 1 and we enqueue it.

We will start our way!!!

For each gene inside our BFS function, we will:

1. Dequeue the current gene: Retrieve the current gene and its associated distance (mutation count) from the queue.

2. Check if we have reached the target: If the current gene is the endGene, we return the corresponding distance as this is the shortest number of mutations.

3. Explore all possible mutations:

   • For each adjacent gene (valid mutation) from the adjacency list, check if it has already been visited by looking it up in the distance dictionary.

   • If the gene hasn’t been visited yet, it means this is the first time we’ve reached it, and since BFS explores layer by layer, this must be the shortest path.

   • Set the distance for this gene to the current distance + 1 and enqueue it for further exploration.

4. Continue exploring: Repeat the above steps until either we find the endGene or the queue is empty.

5. If no valid path is found: Once the queue is exhausted and we haven’t reached the endGene, return -1 to indicate no possible mutation path exists.

Complete code:

 
class Solution {
public:
    map<string,int>distance;
    map<string,vector<string>>adjList; 
    int BFS(string startGene, string endGene){
        queue<string> q;
        distance[startGene] = 1; 
        q.push(startGene);

        while(!q.empty()){
            string currentGene = q.front();
            q.pop();
            for( auto gene: adjList[currentGene]){
                if(distance.find(gene) == distance.end()){ // we havent visited it
                    distance[gene] = distance[currentGene]+1; 
                    q.push(gene);
                }
                if(gene==endGene){
                    return distance[endGene];
                }
            }
        }
         if ( distance.find(endGene) != distance.end()){
            return distance[endGene];
         }
         else{
            return -1; 
         }
         

    }


    int minMutation(string startGene, string endGene, vector<string>& bank) {


        string realStartGene="";
        vector<char> genes = {'A', 'C','G','T' }; 
        
        for(auto mutation: bank){
           for(int i=0; i<mutation.size(); i++){
                string tmpGene=mutation;
                for(auto gene: genes){
                    tmpGene[i]=gene; 
                    if (tmpGene==startGene){ //we found were we really start 
                        realStartGene=mutation; 
                    }
                    if(count(bank.begin(), bank.end(), tmpGene) && (tmpGene!=mutation)){//Mutation exisists in bank and it is not ourselves
                        adjList[mutation].push_back(tmpGene); 
                    }
                }
           }
        }
        
        return BFS(realStartGene, endGene);
        
    }
};

Recommendations

Level up your inbox by subscribing to what I am subscribed to!

Self-gaslight of the week

I truly believe you can gaslight yourself to success.

1. UNLESS IT IS A HECK YES… it is a no!!!!!!!!!!!!

2. The truth about Software Engineering

Jobs and Scholarships

1. New scholarships of this week!

2. Entry level jobs!!