---
# System prepended metadata

title: '**Leetcode筆記(Minimum Genetic Mutation)**'
tags: [graph, medium, leetcode]

---

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


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


### 嘗試
```python

```

---
### **優化**
也是土法煉鋼，一個一個去取字，不需要再建立一個visited，只需要用bank移除加入即可
```python
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. 负雪明烛
