【LeetCode】433.最小基因变化
1. 题目
2. 思想
这题的思想很经典，使用bfs求最短路径。相似的题目还有这道题。
把每次合理的变换都记录在队列中，然后先进先出，同时记录出执行的次数，得到最后的结果。同时需要把历史上曾经入队的基因串都放到字典里，省的重复遍历。
3. 代码
class Solution:def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:que = deque()que.append((startGene,0))vis = set()vis.add(startGene)# 可以转换的目标序列trans = ['A','C','G','T']while(len(que)):# 得从左侧弹出一个数来front, step = que.popleft()# print(front, step)if front == endGene:return step# 从各个维度对front进行修改for i in range(len(front)):for t in trans:new_gene = front[0:i] + t + front[i+1::] if new_gene in bank and new_gene not in vis:# print("new_gene = ",new_gene)vis.add(new_gene)que.append((new_gene, step+1))return -1