433. 最小基因变化

from typing import List, Set


class Solution:
    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
        def mutate(gene: str) -> Set[str]:
            ret = set()
            for i in range(len(gene)):
                ret = ret.union([
                    gene[:i] + 'A' + gene[i + 1:],
                    gene[:i] + 'C' + gene[i + 1:],
                    gene[:i] + 'G' + gene[i + 1:],
                    gene[:i] + 'T' + gene[i + 1:],
                ])
            ret.remove(gene)
            return ret

        bank = set(bank)
        if end not in bank:
            return -1

        if start == end:
            return 0

        visited, s0, ans = {start}, {start}, 0
        while s0:
            s1 = set()
            ans += 1
            for item in s0:
                s1 = s1.union(mutate(item))

            if end in s1:
                return ans

            s0 = s1.intersection(bank).difference(visited)
            visited = visited.union(s0)

        return -1