## 题目描述：

LeetCode 433. Minimum Genetic Mutation

A gene string can be represented by an 8-character long string, with choices from "A","C","G","T".

Suppose we need to investigate about a mutation (mutation from "start" to "end"), where ONE mutation is defined as ONE single character changed in the gene string.

For example, "AACCGGTT" -> "AACCGGTA" is 1 mutation.

Also, there is a given gene "bank", which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.

Now, given 3 things - start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from "start" to "end". If there is no such a mutation, return -1.

For example,

bank: "AACCGGTA"
start: "AACCGGTT"
end: "AACCGGTA"

return: 1

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

return: 3

## Python代码：

``````class Solution(object):
def minMutation(self, start, end, bank):
"""
:type start: str
:type end: str
:type bank: List[str]
:rtype: int
"""
def toNumber(gene):
table = {v : i for i, v in enumerate('ATGC')}
return sum([table[g] * 1 << (2 * i) for i, g in enumerate(gene)])

bank = set(map(toNumber, bank))
start = toNumber(start)
end = toNumber(end)
queue = [(start, 0)]
viset = set([start])
while queue:
gene, step = queue.pop(0)
if gene == end:
return step
for x in range(8):
for y in range(4):
next = gene ^ (y << (x * 2))
if next in bank and next not in viset:
queue.append((next, step + 1))
return -1
`````` Pingbacks已关闭。

1. 浙江经济理事会 发布于 2016年10月21日 09:58 #

Python好像很热门啊，好学吗？