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
, andbank[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[0]
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
}