LeetCode 题解:433. 最小基因变化,DFS,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 12 月 13 日
LeetCode题解:433. 最小基因变化,DFS,JavaScript,详细注释

原题连接:https://leetcode-cn.com/problems/minimum-genetic-mutation/



解题思路:



  1. 理解题意:

* 该题要求从bank中查找基因从start变化到end的最小次数。

* 基因每次只能变化一个字符。

* 变化的路径不是唯一的。

  1. 使用DFS:

* 每次递归都从bank中选取与当前基因相比,只变化一个字符的基因,将其作为中间结果,进入下层递归。

* 为保证不重复选取bank中的元素,使用Set标识bank中的元素是否被访问过。

* 遇到中间结果与end相等,即为找到一条可能的变化路径。

* 由于路径不止一条,因此变化次数要取最小值。

  1. 重要的Case:

"AACCGGTT"
"AAACGGTA"
["AACCGATT","AACCGATA","AAACGATA","AAACGGTA"]



"AAAACCCC"
"CCCCCCCC"
["AAAACCCA","AAACCCCA","AACCCCCA","AACCCCCC","ACCCCCCC","CCCCCCCC","AAACCCCC","AACCCCCC"]



/**
* @param {string} start
* @param {string} end
* @param {string[]} bank
* @return {number}
*/
var minMutation = function (start, end, bank) {
let used = new Set(); // 标识bank是否被访问过
let min = Infinity; // 存储结果,默认为Infinity,避免取最小值是出错
// 使用DFS查找所有可能的变化路径
function dfs(
str, // 基因每次变化的中间结果
count, // 基因变化次数
) {
// 递归终止条件
// 当基因变化到目标时,表示已经找到变化次数
if (str === end) {
// 由于可能会找到多种变化方式,因此需要取最小值
min = Math.min(count, min);
return;
}
// 当前层递归逻辑
// 由于可能的变化路径会是在bank中随机选取,因此每次都从0开始遍历bank
for (let i = 0; i < bank.length; i++) {
// 如果当前值已经被使用过,继续匹配下一个
if (used.has(bank[i])) {
continue;
}
let diff = 0; // 统计str与bank[i]的差异,为1则表示其是可能的一次变化
// 遍历bank[i]的每个字符
for (let j = 0; j < bank[i].length; j++) {
// 当str与bank[i]的字符不一致时,记录基因变化次数
if (str[j] !== bank[i][j]) {
diff++;
// 如果差异大于1,表示变化了2次,bank[i]不是可能的变化,退出循环
if (diff > 1) {
break;
}
}
}
// 进入下层递归
// 由于题目要求基因每次只能变化一个字符,因此只有diff为1才可进入下一层递归
if (diff === 1) {
// 标识bank[i]已被使用过
used.add(bank[i]);
// 进入下一层递归,bank[i]即为当前层变化结果,将变化次数加1
dfs(bank[i], count + 1);
// 清除当前递归状态
// 清除bank[i]的使用状态,提供给下一次for循环使用
used.delete(bank[i]);
}
}
}
// 从起始基因序列开始DFS查找,初始变化次数为0
dfs(start, 0);
// 如果min为Infinity,表示未找到结果,返回-1,否则返回min
return min === Infinity ? -1 : min;
};



发布于: 2020 年 12 月 13 日阅读数: 11
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:433. 最小基因变化,DFS,JavaScript,详细注释