MinimumGeneticMutation.py

# Question link - https://leetcode.com/problems/minimum-genetic-mutation/?envType=study-plan-v2&envId=top-interview-150

from typing import List
import collections


class Solution:
    # helper function to check if difference is exactly one
    def isDiff(self, s1, s2):
        if len(s1) != len(s2):
            return False
        cnt = 0
        for i in range(len(s1)):
            if s1[i] != s2[i]:
                cnt += 1
        return cnt == 1

    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        # If endGene is not in bank, it's impossible
        if endGene not in bank:
            return -1
            
        # Create the adj map using a dictionary instead of a list
        adj = {}
        
        # Initialize adjacency lists for all genes
        adj[startGene] = []
        for gene in bank:
            adj[gene] = []
        
        # Connect bank genes to each other
        for i in range(len(bank)):
            for j in range(i + 1, len(bank)):
                if self.isDiff(bank[i], bank[j]):
                    adj[bank[i]].append(bank[j])
                    adj[bank[j]].append(bank[i])
        
        # Connect startGene to bank genes
        for gene in bank:
            if self.isDiff(startGene, gene):
                adj[startGene].append(gene)
                adj[gene].append(startGene)

        # BFS
        q = collections.deque()
        q.append((startGene, 0))
        visited = set()
        visited.add(startGene)
        
        while q:
            node, level = q.popleft()
            if node == endGene:
                return level
            for nei in adj[node]:
                if nei not in visited:
                    visited.add(nei)
                    q.append((nei, level + 1))

        return -1  # if not found