Minimum Genetic Mutation

Intuition

Solution

class Solution:
    def _neighbours(self, s):
        for i in range(8):
            for c in 'ATCG':
                if c == s[i]:
                    continue
                yield s[:i] + c + s[i+1:]

    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
        bank = set(bank)
        current = [start]
        visited = set(current)
        depth = 0
        while current:
            tmp = []
            for node in current:
                for neighbour in self._neighbours(node):
                    if neighbour not in bank:
                        continue
                    if neighbour in visited:
                        continue
                    if neighbour == end:
                        return depth + 1
                    visited.add(neighbour)
                    tmp.append(neighbour)
            current = tmp
            depth += 1
        return -1