Leetcode 433 Solution

This article provides solution to leetcode question 433 (minimum-genetic-mutation)

https://leetcode.com/problems/minimum-genetic-mutation

Solution

class Solution:
    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
        bank = set(bank)

        q = collections.deque()
        q.append(start)
        seen = {start}

        step = 0
        while q:
            s = len(q)
            for _ in range(s):
                cur = q.popleft()

                if cur == end:
                    return step

                for ch in ["A", "C", "G", "T"]:
                    for i in range(len(cur)):
                        if cur[i] == ch:
                            continue
                        next_gene = cur[0:i] + ch + cur[i + 1:]
                        if next_gene in bank and next_gene not in seen:
                            q.append(next_gene)
                            seen.add(next_gene)

            step += 1

        return -1