leetcode-433

2020-05-09 阅读量

字数统计: 456字 | 阅读时长: 1分

题目 leetcode-433

一条基因序列由一个带有8个字符的字符串表示，其中每个字符都属于 “A”, “C”, “G”, “T”中的任意一个。
假设我们要调查一个基因序列的变化。一次基因变化意味着这个基因序列中的一个字符发生了变化。
例如，基因序列由”AACCGGTT” 变化至 “AACCGGTA” 即发生了一次基因变化。
与此同时，每一次基因变化的结果，都需要是一个合法的基因串，即该结果属于一个基因库。
现在给定3个参数 — start, end, bank，分别代表起始基因序列，目标基因序列及基因库，请找出能够使起始基因序列变化为目标基因序列所需的最少变化次数。
如果无法实现目标变化，请返回 -1。

注意:

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

用例

start: “AACCGGTT”
end: “AACCGGTA”
bank: [“AACCGGTA”]

返回值: 1

start: “AACCGGTT”
end: “AAACGGTA”
bank: [“AACCGGTA”, “AACCGCTA”, “AAACGGTA”]

返回值: 2

start: “AAAAACCC”
end: “AACCCCCC”
bank: [“AAAACCCC”, “AAACCCCC”, “AACCCCCC”]

返回值: 3

解题思想

bfs或者dfs遍历列表中所有可能的值

###代码

class Solution:
    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
        from collections import deque
        bank = set(bank)
        if end not in bank:
            return -1
        visited = set()
        visited.add(start)
        mutation = {"A", "C", "G", "T"}

        # 产生只差一个字母的基因
        def oneMutation(cur):
            for i, val in enumerate(cur):
                for t in mutation - {val}:
                    tmp = cur[:i] + t + cur[i + 1:]
                    if tmp in bank:
                        yield tmp

        queue = deque()
        queue.appendleft([start, 0])
        while queue:
            cur, res = queue.pop()
            if cur == end:
                return res
            for nxt in oneMutation(cur):
                if nxt not in visited:
                    visited.add(nxt)
                    queue.appendleft((nxt, res + 1))
        return -1