题目描述：

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

题目大意：

一个基因字符串可以用8个字符组成的字符串表示，每个字符可以是"A","C","G","T"。

加入我们需要研究基因突变（从"start"到"end"的突变），其中一次突变是指基因字符串中的某一个位置字符的改变。

例如"AACCGGTT" -> "AACCGGTA"是1次突变。

并且，给定一个基因“银行”，记录了所有有效的基因突变。只有突变成银行中的基因才是有效基因。

现在，给定3个参数-start, end, bank。你的任务是求出从start到end的最少突变次数。如果不存在则返回-1。

解题思路：

进制转换+位运算+广度优先搜索（BFS）

用4进制将基因字符串转化为整数，通过BFS可以求出最少突变次数，每一次突变的转换可以用异或运算完成。

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:
                        viset.add(next)
                        queue.append((next, step + 1))
        return -1

 

本文链接：http://bookshadow.com/weblog/2016/10/20/leetcode-minimum-genetic-mutation/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码