[BFS] LeetCode 433. Minimum Genetic Mutation

Solution using BFS O(len(bank))^2 * len(gene))

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        q = deque([(startGene,0)])
        visited = [False] * len(bank)

        while q:
            currentGene, cost = q.popleft()

            if currentGene == endGene:
                return cost

            for i in range(len(bank)):
                gene = bank[i]
                if not visited[i]:
                    diff = 0
                    for j in range(len(gene)):
                        if currentGene[j] != gene[j]:
                            diff += 1
                        if diff > 1:
                            break
                    if diff == 1:
                        visited[i] = True
                        q.append((gene, cost + 1))

        return -1

This is a simple BFS problem. We can think as the startGene as starting node and endGene as ending node. For the genes in the bank, we can think of them as nodes connected to the startGene. A gene is directly connected to another gene if they have only one difference in their genes. So, each time we check its neighbors, we only include the ones that are directly connected to the current gene. If we can reach the end gene, we return the cost. If there isn’t, we return -1.