## 題解

### BFS

使用 BFS 窮舉所有字串組合

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        queue = [(startGene,0)]
        if startGene == endGene:
            return 0
        
        bank = set(bank)
        if endGene not in bank:
            return -1

        while queue:
            gene, mu = queue.pop(0)
            for s in range(len(gene)):
                for g in "ACGT":
                    if g != gene[s]:
                        new_gene = gene[:s] + g + gene[s+1:] 
                        if new_gene in bank:
                            if new_gene == endGene:
                                return mu + 1
                            bank.remove(new_gene)
                            queue.append((new_gene,mu + 1))
        return -1