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