38 lines
1.3 KiB
Python
38 lines
1.3 KiB
Python
class Solution:
|
|
def minMutation(self, startGene: str, endGene: str, bank: list[str]) -> int:
|
|
if endGene not in bank: return -1
|
|
que = []
|
|
front = -1
|
|
tail = -1
|
|
def push_back(que, front, tail, ele):
|
|
tail += 1
|
|
if tail >= len(que):
|
|
que.append(ele)
|
|
else:
|
|
que[tail] = ele
|
|
return tail
|
|
def pop(que, front ,tail):
|
|
front += 1
|
|
return (front , que[front])
|
|
tail = push_back(que,front,tail,(startGene,0))
|
|
def diff(str1, str2) -> int:
|
|
rlt = 0
|
|
for idx, ch in enumerate(str1):
|
|
if(str1[idx] != str2[idx]): rlt += 1
|
|
return rlt
|
|
rlt = 1e5
|
|
while front != tail:
|
|
(front, top_ele) = pop(que, front, tail)
|
|
step = top_ele[1]
|
|
string = top_ele[0]
|
|
if diff(string, endGene) == 0: return step
|
|
for s in bank:
|
|
diff_num = diff(s, string)
|
|
# print(diff_num)
|
|
if diff_num == 1:
|
|
tail = push_back(que, front, tail, (s, step + 1))
|
|
return -1
|
|
|
|
sol = Solution()
|
|
print(sol.minMutation("AACCGGTT","AACCGGTA",["AACCGGTA"]))
|
|
print(sol.minMutation("AACCGGTT","AAACGGTA",["AACCGGTA","AACCGCTA","AAACGGTA"])) |