原题连接：https://leetcode-cn.com/problems/minimum-genetic-mutation/
解题思路：
理解题意：
* 该题要求从 bank 中查找基因从 start 变化到 end 的最小次数。
* 基因每次只能变化一个字符。
* 变化的路径不是唯一的。
使用 BFS：
* 使用 Set 保存 bank 中的基因，如果其中的基因被使用过，则将其删除，可以避免重复选着。
* 使用队列进行遍历，队列中按顺序存储了每一层的元素。
* 每次循环时，将队列中当前层的元素依次取出，然后生成所有可能的基因变化情况。
* 如果新生成的基因在 Set 中，表示它是下一步的变化，将其存入队列，同时从 Set 中删除。
* 由于 BFS 是逐层进行遍历，一旦遇到有序列与目标序列相等，即为找到了最小变化次数，可以退出循环。
重要的 Case：
"AACCGGTT""AAACGGTA"["AACCGATT","AACCGATA","AAACGATA","AAACGGTA"]
复制代码
"AAAACCCC""CCCCCCCC"["AAAACCCA","AAACCCCA","AACCCCCA","AACCCCCC","ACCCCCCC","CCCCCCCC","AAACCCCC","AACCCCCC"]
复制代码
"AAAAAAAA""CCCCCCCC"["AAAAAAAA","AAAAAAAC","AAAAAACC","AAAAACCC","AAAACCCC","AACACCCC","ACCACCCC","ACCCCCCC","CCCCCCCA"]
复制代码
/** * @param {string} start * @param {string} end * @param {string[]} bank * @return {number} */var minMutation = function (start, end, bank) { let level = 0; // 统计BFS遍历的深度 let queue = [start]; // 在队列中存储起始基因序列，用于开始循环 let bankSet = new Set(bank); // 存储未被访问过的基因序列 let charBank = ['A', 'T', 'C', 'G']; // 每个基因可变化的字母
// 不断遍历队列，直到队列为空时，完成BFS while (queue.length) { // 缓存当前队列中的元素数量，即为当前层的元素数量 let queueLength = queue.length;
// 进行queueLength次遍历 while (--queueLength >= 0) { // 将队列中的当前基因出队 const currGene = queue.pop();
// 遍历当前基因的字母 for (let i = 0; i < currGene.length; i++) { // 从当前可变化字母中寻找一个可用的字母 for (let j = 0; j < charBank.length; j++) { // 避免生成与当前基因重复的序列 if (charBank[j] === currGene[i]) { continue; }
// 生成一个新基因序列 const newGene = `${currGene.slice(0, i)}${ charBank[j] }${currGene.slice(i + 1)}`;
// 判断新基因是否使用 if (bankSet.has(newGene)) { // 如果第一次发现，新基因与目标相同，表示查找到了最短变化路径 if (newGene === end) { // 由于当前变化没有被计数，返回结果时需要加1 return ++level; }
// 将当前基因从Set中删除，表示其被访问过 bankSet.delete(newGene); // 将当前基因存入数组，用于下一次变化 queue.push(newGene); } } } }
// 每完成一层遍历之后，变化数量就加1 level++; }
// 如果退出循环，表示未找到变化路径，直接返回-1 return -1;};
复制代码
评论