# LeetCode: 433. 最小基因变化¶

## 1、题目描述¶

1. 起始基因序列默认是合法的，但是它并不一定会出现在基因库中。
2. 所有的目标基因序列必须是合法的。
3. 假定起始基因序列与目标基因序列是不一样的。

start: "AACCGGTT"
end:   "AACCGGTA"
bank: ["AACCGGTA"]



start: "AACCGGTT"
end:   "AAACGGTA"
bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]



start: "AAAAACCC"
end:   "AACCCCCC"
bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]



## 2、解题思路¶

​ 这道题跟127题很相似,直接应该使用广度优先搜索来做，直接使用127提的解法就可以

start: "AACCGGTT"
end:   "AACCGGTA"
bank: ["AACCGGTA"]

{"AACCGGT_":["AACCGGTA"]}


class Solution(object):
def minMutation(self, start, end, bank):
"""
:type start: str
:type end: str
:type bank: List[str]
:rtype: int
"""
d = {}
for gene in bank:
for i in range(len(gene)):
s = gene[:i] + "_" + gene[i + 1:]
d[s] = d.get(s, []) + [gene]

visited = set([start])
temp = set()
not_visited = set(bank)
count = 0
while visited:
for i in visited:
for j in range(len(i)):
s = i[:j] + "_" + i[j + 1:]
temp = temp.union(set(d.get(s, [])))
d.pop(s, 0)
if len(temp) == 0:
return -1

count += 1
if end in temp:
return count

not_visited = not_visited - temp
visited = temp
temp = set()

return -1