Minimum Genetic Mutation - Leetcode Solution

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.

1