LeetCode_433_0041.py

# 一条基因序列由一个带有8个字符的字符串表示，其中每个字符都属于 "A", "C", "G", "T"中的任意一个。
#
# 假设我们要调查一个基因序列的变化。一次基因变化意味着这个基因序列中的一个字符发生了变化。
#
# 例如，基因序列由"AACCGGTT" 变化至 "AACCGGTA" 即发生了一次基因变化。
#
# 与此同时，每一次基因变化的结果，都需要是一个合法的基因串，即该结果属于一个基因库。
#
# 现在给定3个参数 — start, end, bank，分别代表起始基因序列，目标基因序列及基因库，请找出能够使起始基因序列变化为目标基因序列所需的最少变化次数。如果无法实现目标变化，请返回 -1。
#
# 注意:
#
#
# 起始基因序列默认是合法的，但是它并不一定会出现在基因库中。
# 所有的目标基因序列必须是合法的。
# 假定起始基因序列与目标基因序列是不一样的。
#
#
# 示例 1:
#
#
# start: "AACCGGTT"
# end:   "AACCGGTA"
# bank: ["AACCGGTA"]
#
# 返回值: 1
#
#
# 示例 2:
#
#
# start: "AACCGGTT"
# end:   "AAACGGTA"
# bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]
#
# 返回值: 2
#
#
# 示例 3:
#
#
# start: "AAAAACCC"
# end:   "AACCCCCC"
# bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]
#
# 返回值: 3
#
#


# leetcode submit region begin(Prohibit modification and deletion)
from typing import List


class Solution:
    def minMutation(self, start: str, end: str, _bank: List[str]) -> int:
        bank = set(_bank)
        level = 0
        queue = [start]
        visitor = set([start])
        LEN = len(start)

        while queue:
            next_queue = []
            for current_mutation in queue:
                if current_mutation == end:
                    return level
                for i in range(LEN):
                    for c in "AGCT":
                        next_mutation = current_mutation[:i] + c + current_mutation[i + 1:]
                        if next_mutation in bank and next_mutation not in visitor:
                            visitor.add(next_mutation)
                            next_queue.append(next_mutation)
            level += 1
            queue = next_queue

        return -1
    def minMutationTwoBFS(self, start: str, end: str, bank: List[str]) -> int:
        front, back, visitor = set([start]), set([end]), set()
        cnt = 0
        while front:
            next_queue = set()
            for mutation in front:
                visitor.add(mutation)
                for i in range(len(mutation)):
                    for c in "ACGT":
                        if c != mutation[i]:
                            next_mutation = mutation[:i] + c + mutation[i + 1:]
                            if next_mutation in bank:
                                if next_mutation in back:
                                    return cnt + 1
                                if next_mutation not in visitor:
                                    next_queue.add(next_mutation)
            cnt += 1
            front = next_queue
            if len(front) > len(back):
                back, front = front, back
        return -1



# leetcode submit region end(Prohibit modification and deletion)
print(Solution().minMutation("AACCGGTT", "AACCGCTA", ["AACCGGTA", "AACCGCTA", "AAACGGTA"]))