Problem
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.
link: https://leetcode.com/problems/minimum-genetic-mutation/description/
Note: also twitter OA
Python Solution:
def minMutation(self, start, end, bank):
"""
:type start: str
:type end: str
:type bank: List[str]
:rtype: int
"""
q = {start}
visited = set()
bank = set(bank)
n = len(end)
level = 0
while q:
new_q = set()
while q:
elem = q.pop()
if elem == end:
return level
visited.add(elem)
for i in range(n):
for ch in ('A','T','C','G'):
temp = elem[:i] + ch + elem[i+1:]
if temp in bank and temp not in visited:
new_q.add(temp)
q = new_q
level += 1
return -1
Complexity Analysis:
time: O( 8*4 + bank_size)
space: O(bank_size)