# **Leetcode筆記(Minimum Genetic Mutation)**

:::info
:information_source: 題目 : Minimum Genetic Mutation, 類型 : graph , 等級 : medium
日期 : 2023/10/14
:::

### 嘗試

---
### **優化**
也是土法煉鋼，一個一個去取字，不需要再建立一個visited，只需要用bank移除加入即可

class Solution:
    def __init__(self):
        self.res_step = -1
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:

        def bfs(curGene, step):
            if curGene == endGene:
                self.res_step = step
                return 
            
            if self.res_step != -1:
                return
            
            for i in range(len(startGene)):
                for c in "ACGT":
                    testGene = curGene[:i] + c + curGene[i + 1:]
                    if testGene in bank and testGene != curGene:
                        bank.remove(testGene)
                        bfs(testGene, step + 1) 
                        bank.append(testGene)
                        
        bfs(startGene, 0)

        return self.res_step

---

**思路**

**講解連結**
https://blog.csdn.net/fuxuemingzhu/article/details/82903720
Provided by. 负雪明烛