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

大师

大师

大帅