题解 | #基因变异最小次数#

• 题目考察的知识点 : 哈希，BFS
• 题目解答方法的文字分析：

1. 使用集合 bank 存储基因库中的所有基因。如果 end 不在 bank 中，则无法完成基因变化，直接返回 -1。
2. 将 (start, 0) 加入队列 queue，并将其标记为已访问 visited。
3. 遍历队列 queue 中的元素，对于其中的每个元素 (curr, step)，进行如下操作：如果 curr 等于 end，则返回步数 step。否则遍历 curr 的每个字符，对于其中的每个字符，使用 A、C、G、T 进行替换，得到新的字符串 next_gene。如果 next_gene 在 bank 中，并且没有被访问过，则将 (next_gene, step+1) 加入队列并标记为已经访问 visited。
4. 如果队列为空，则说明无法从 start 变化为 end，返回 -1。

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param start string字符串
# @param end string字符串
# @param bank string字符串一维数组
# @return int整型
#
from collections import deque
class Solution:
    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
        bank = set(bank)
        if end not in bank:
            return -1

        queue = deque([(start, 0)])
        visited = set([start])

        while queue:
            curr, step = queue.popleft()
            if curr == end:
                return step
            for i in range(8):
                for c in "ACGT":
                    next_gene = curr[:i] + c + curr[i + 1 :]
                    if next_gene in bank and next_gene not in visited:
                        queue.append((next_gene, step + 1))
                        visited.add(next_gene)
        return -1