Similar Problems
Similar Problems not available
Minimum Genetic Mutation - Leetcode Solution
Companies:
LeetCode: Minimum Genetic Mutation Leetcode Solution
Difficulty: Medium
Topics: string hash-table breadth-first-search
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.
Minimum Genetic Mutation Solution Code
1