Problem of The Day: Minimum Genetic Mutation

Problem Statement

leetcode problem link

BFS [Accepted]

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        queue = deque()
        queue.append([startGene, 0])
        N = len(startGene)
        seen = set()
        seen.add(startGene)
        while queue:
            node, mutations = queue.popleft()
            if node == endGene:
                return mutations
            for i in range(N):
                for nei in 'ACGT':
                    if nei != node[i]:
                        temp = list(node)
                        temp[i] = nei
                        temp_str = ''.join(temp)
                        if temp_str not in seen and temp_str in bank:
                            queue.append([temp_str, mutations + 1])
                            seen.add(temp_str)

        return -1

Editorial

Approach: BFS (Breadth-First Search)

class Solution:
    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
        queue = deque([(start, 0)])
        seen = {start}

        while queue:
            node, steps = queue.popleft()
            if node == end:
                return steps

            for c in "ACGT":
                for i in range(len(node)):
                    neighbor = node[:i] + c + node[i + 1:]
                    if neighbor not in seen and neighbor in bank:
                        queue.append((neighbor, steps + 1))
                        seen.add(neighbor)

        return -1