# 433. Minimum Genetic Mutation

Medium
A gene string can be represented by an 8-character long string, with choices from `'A'`, `'C'`, `'G'`, and `'T'`.
Suppose we need to investigate a mutation from a gene string `start` to a gene string `end` where one mutation is defined as one single character changed in the gene string.
• For example, `"AACCGGTT" --> "AACCGGTA"` is one mutation.
There is also a gene bank `bank` that records all the valid gene mutations. A gene must be in `bank` to make it a valid gene string.
Given the two gene strings `start` and `end` and the gene bank `bank`, return the minimum number of mutations needed to mutate from `start` to `end`. If there is no such a mutation, return `-1`.
Note that the starting point is assumed to be valid, so it might not be included in the bank.
Example 1:
Input: start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
Output:
1
Example 2:
Input: start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
Output:
2
Example 3:
Input: start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
Output:
3
Constraints:
• `start.length == 8`
• `end.length == 8`
• `0 <= bank.length <= 10`
• `bank[i].length == 8`
• `start`, `end`, and `bank[i]` consist of only the characters `['A', 'C', 'G', 'T']`.

### 解題

BFS 來解題
Runtime: 1 ms, faster than 54.55%
Memory Usage: 1.9 MB, less than 100.00%
func minMutation(start string, end string, bank []string) int {
bankMap := make(map[string]bool)
for _, word := range bank {
bankMap[word] = true
}
queue := []string{ start }
chars := []byte{ 'A', 'T', 'C', 'G' }
res := 0
for len(queue) > 0 {
n := len(queue)
for i := 0; i < n; i++ {
cur := queue
queue = queue[1:] // 移除第一個
if cur == end { return res }
for j:=0; j< 8; j++ {
for _, char := range chars {
newStr := cur[:j] + string(char) + cur[j+1:]
if bankMap[newStr] {
queue = append(queue, newStr)
delete(bankMap, newStr)
}
}
}
}
res++
}
return -1
}