楼主:
pandix (面包屌)
2022-11-02 15:12:54433. Minimum Genetic Mutation
龙大体内的基因突变了。给你开始和目标基因以及合法基因，问突变至目标基因要花几步
基因是长度为8 由"ACGT"组成的字串
基因突变:改变基因中的一个字符 ex: "AACCGGTT" -> "AACCGGTA"
过程中只能突变至合法基因中有的基因
Example 1:
Input: start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1
Example 2:
Input: start = "AACCGGTT", end = "AAACGGTA", bank =
["AACCGGTA","AACCGCTA","AAACGGTA"]
Output: 2
Example 3:
Input: start = "AAAAACCC", end = "AACCCCCC", bank =
["AAAACCCC","AAACCCCC","AACCCCCC"]
Output: 3
思路:
1.总之先建 set 存那些合法基因，因为问最短步数所以就用BFS
每轮检查目前走到的基因中有哪些突变后的结果在合法基因中
有就加进下一轮要检查的基因
2.走到之后可以直接把他移出合法基因代表他已经走过了不用再走了
可以省下一般 BFS 中要用的 visited
3.
Python code:
class Solution:
def minMutation(self, start: str, end: str, bank: List[str]) -> int:
bankset = set(bank)
currstep, nextstep = [start], []
step = 0
while currstep:
for gene in currstep:
if gene == end:
return step
for i in range(8):
for c in 'ACGT':
newgene = gene[:i] + c + gene[i+1:]
if newgene in bankset:
nextstep.append(newgene)
bankset.remove(newgene)
currstep, nextstep = nextstep, []
step += 1
return -1