433. Minimum Genetic Mutation
https://leetcode.com/problems/minimum-genetic-mutation/
題意
每一段字串代表一個基因序列，基因在變化的時候，每次只會變化一個字，只要變化的過程以及變化結束的時候，都在 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 的筆記本 留言，順手給我個讚吧！你的讚將成為我持續更新的動力，感謝你的閱讀，讓我們一起學習成為更好的自己。