433. Minimum Genetic Mutation
https://leetcode.com/problems/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 == 8end.length == 80 <= bank.length <= 10bank[i].length == 8start,end, andbank[i]consist of only the characters['A', 'C', 'G', 'T'].
題意
每一段字串代表一個基因序列，基因在變化的時候，每次只會變化一個字，只要變化的過程以及變化結束的時候，都在 bank 庫中找得到就好，最後要回傳基因變化了幾次，如果不在庫中的話，要回傳 -1 。
解題思路
我們從 start 開始走，每次在 bank 中找看看是否有變化一個字的基因，如果有再塞入 queue 中，然後再檢查 queue 中的值，是否等於 end ，當 queue 被消耗完畢還是沒有訪問到 end 的話，代表找不到回傳 -1 。
- 撰寫一個 contains 方法，用於確認基因序列是不是在 bank 中。
- 撰寫一個 canMutate 方法，用於確認基因是不是只有變化一個字。
- 宣告一個 queue。
- 宣告一個訪問過的元素，用於確保 bank 中的基因，不會被重複訪問。
- 宣告一個 ans ，記錄基因變化的次數。
- 開始遍歷 queue 中的基因，每次取出一個，只要基因剛好等於 end 時，就回傳 ans 。
- 如果基因不等於 end 的話，就把尚未訪問過的 bank 中的基因挑出來，判定一下是否基因的變化只發生一個字，如果是就塞入 queue 中，讓下個循環去判定結果。
原始碼
func minMutation(start string, end string, bank []string) int {
queue := []string{}
visited := make(map[string]bool, 0)
if contains(bank, end) && start == end {
return -1
}
queue = append(queue, start)
visited[start] = true
ans := 0
for len(queue) != 0 {
length := len(queue)
for i := 0; i < length; i++ {
current := queue[0]
queue = queue[1:]
if current == end {
return ans
}
for _, b := range bank {
if canMutate(b, current) && !visited[b] {
queue = append(queue, b)
visited[b] = true
}
}
}
ans++
}
return -1
}
func canMutate(str1, str2 string) bool {
counter := 0
for i := 0; i < len(str1); i++ {
if str1[i] != str2[i] {
counter++
}
}
return counter == 1
}
func contains(bank []string, tofind string) bool {
for _, b := range bank {
if tofind == b {
return true
}
}
return false
}
結尾
你有更好或更簡單的解決方案嗎？
歡迎到我的 Facebook Alan 的筆記本 留言，順手給我個讚吧！你的讚將成為我持續更新的動力，感謝你的閱讀，讓我們一起學習成為更好的自己。
