This page looks best with JavaScript enabled

# Leetcode 433 Minimum Genetic Mutation

## 題目

A gene string can be represented by an 8-character long string, with choices from “A”, “C”, “G”, “T”.

Suppose we need to investigate about a mutation (mutation from “start” to “end”), where ONE mutation is defined as ONE single character changed in the gene string.

For example, "AACCGGTT" -> "AACCGGTA" is 1 mutation.

Also, there is a given gene “bank”, which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.

Now, given 3 things - start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from “start” to “end”. If there is no such a mutation, return -1.

Note:

1. Starting point is assumed to be valid, so it might not be included in the bank.
2. If multiple mutations are needed, all mutations during in the sequence must be valid.
3. You may assume start and end string is not the same.

Example 1:

start: "AACCGGTT"
end:   "AACCGGTA"
bank: ["AACCGGTA"]

return: 1


Example 2:

start: "AACCGGTT"
end:   "AAACGGTA"
bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]

return: 2


Example 3:

start: "AAAAACCC"
end:   "AACCCCCC"
bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]

return: 3


Accepted 35,543 | Submissions 83,045

## 思路&過程

1. 從 start 開始，若 bank 中有與 start 差異為 1，把它從 bank 中移除，紀錄在另一個地方，供再次比對
2. 紀錄的 ds 為 walked 這個 set()。為了構成迴圈， 一開始就把 start 放入 walked ，每次回圈開始前檢查 end 是否有在 walked 裡面
3. while loop 何時該停止？
• 若該次 bank 內沒有東西要移動
• walked 中已經有 end 了
• bank 被取光

### 處理細節

• 排除 bank = [] 的狀況 (偶爾會忘記 LC 老把戲)
• 製作判斷鹼基差異的 method
1. 使用 index 比對兩字串
2. 若第一次不同: 記下來；第二次直接 return False
• 用來記錄移動的 bgt_move 選擇 set() ， 原因如下：
1. 方便操作:搬進walked & 從bank移除，所以讓 bgt_move、 bank、 walked 三者使用同種 ds
2. 選擇 set() 的原因:
• walked 在 while loop 使用到了in判斷
• bank 可能很白目的有大量重複
• 兩層 for loop 讓 bank 在外層，因 bank 每個元素都要處理到，但 walked 不用

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29  class Solution: def minMutation(self, start: str, end: str, bank: List[str]) -> int: if not bank: return -1 bank, walked = set(bank), {start} re = 0 while end not in walked and bank: bgt_move = set() # will be moved for b in bank: for w in walked: if self.only_one_diff(b, w): bgt_move.add(b) break if not bgt_move: return -1 bank -= bgt_move walked |= bgt_move re += 1 return re @staticmethod def only_one_diff(a, b): fond_diff = False for i in range(len(a)): if a[i] != b[i]: if fond_diff: return False fond_diff = True return True 

### testcase

s = "AACCTTGG"
e = "AATTCCGG"
b = []
t = Solution().minMutation(s, e, b)
print(t)

s = "AACCGGTT"
e = "AACCGGTA"
b = ["AACCGGTA"]
t = Solution().minMutation(s, e, b)
print(t)

s = "AACCGGTT"
e = "AAACGGTA"
b = ["AACCGGTA", "AACCGCTA", "AAACGGTA"]
t = Solution().minMutation(s, e, b)
print(t)

s = "AAAAACCC"
e = "AACCCCCC"
b = ["AAAACCCC", "AAACCCCC", "AACCCCCC"]
t = Solution().minMutation(s, e, b)
print(t)

s = "AACCTTGG"
e = "AATTCCGG"
b = ["AATTCCGG", "AACCTGGG", "AACCCCGG", "AACCTACC"]
t = Solution().minMutation(s, e, b)
print(t)