Re: [閒聊] 每日LeetCode已回收
433. Minimum Genetic Mutation
給與兩個長度8的字串陣列，他由4種字母組成，分別表示基因的序列，基因有一定機率會
突變，每次突變時可改變一個字母，求出從start的基因突變到end的基因需要突變的最小
次數，其中突變的基因他必須包含在字串陣列bank[]之中，如果無法突變成結果的基因則
返回-1。
Example
Input: start = "AACCGGTT", end = "AAACGGTA", bank =
["AACCGGTA","AACCGCTA","AAACGGTA"]
Output: 2
Explain：
(Start) (End)
AACCGGTT -> AACCGGTA -> AAACGGTA -> AAACGGTA
思路：
1.因為給的測資很小(長度小於8、數量最多10)所以採回溯法求解。
2.類似排列問題的解法，利用一個陣列來記錄哪個銀行沒有走過，並窮舉出所有
可能的走法，若cur等於target時才返回並更新答案。
JavaCode：
class Solution {
public int minMutation(String start, String end, String[] bank) {
return backTracking(start, end, bank, new boolean[bank.length], 0);
}
private int backTracking(String cur, String target, String[] bank,
boolean[] visited, int count) {
if(cur.equals(target))
return count;
int ans = Integer.MAX_VALUE;
for(int i = 0; i < bank.length; i++) {
// 如果沒走訪過則利用函數檢查他是否可走訪(恰好差一個字母)
if (visited[i] || !isValid(cur, bank[i]))
continue;
visited[i] = true;
int res = backTracking(bank[i], target, bank, visited, count + 1);
if(res != -1) ans = Math.min(ans, res);
visited[i] = false;
}
return (ans == Integer.MAX_VALUE) ? -1 : ans;
}
private boolean isValid(String s1, String s2) {
int count = 0;
for(int i = 0; i < s1.length(); i++) {
if(s1.charAt(i) != s2.charAt(i)) count++;
if(count > 1) return false;
}
return true;
}
}
自S
https://i.imgur.com/nYPrAZB.png
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.159.111.108 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1667392112.A.ED1.html
→
11/02 20:30,
3年前
, 1F
11/02 20:30, 1F
※ 編輯: Rushia (49.159.111.108 臺灣), 11/02/2022 20:32:23
推
11/02 20:42,
3年前
, 2F
11/02 20:42, 2F
→
11/02 20:51,
3年前
, 3F
11/02 20:51, 3F
討論串 (同標題文章)
完整討論串 (本文為第 81 之 719 篇)：