最小基因变化

开启掘金成长之旅！这是我参与「掘金日新计划 · 12 月更文挑战」的第26天，点击查看活动详情

433. 最小基因变化 – 力扣（Leetcode）

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。

假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

• 例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。

另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。

给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。

注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。

示例 1：

输入： start = “AACCGGTT”, end = “AACCGGTA”, bank = [“AACCGGTA”]
输出： 1

示例 2：

输入： start = “AACCGGTT”, end = “AAACGGTA”, bank = [“AACCGGTA”,”AACCGCTA”,”AAACGGTA”]
输出： 2

示例 3：

输入： start = “AAAAACCC”, end = “AACCCCCC”, bank = [“AAAACCCC”,”AAACCCCC”,”AACCCCCC”]
输出： 3

提示：

• start.length == 8
• end.length == 8
• 0 <= bank.length <= 10
• bank[i].length == 8
• start、end 和 bank[i] 仅由字符 ['A', 'C', 'G', 'T'] 组成

思路

本题可以使用广度优先遍历和深度优先遍历求解，这里说一下广度优先遍历的思路。根据题目要求知道，当start === end的时候，基因不用变异，返回0。当end不包含在bank中时，end变异不合法，返回-1。我们以start为起始基因，遍历bank找到所有可以从start经过一次变异可以得到的基因数组，并在bank中标记这些基因，再以得到的基因数组为起点，遍历bank中未被标记的基因，找到新的可以一次变异的基因数组，直到新得到的基因组中包含end基因或新基因组为空，如解法一。

至于深度优先，这里就不再赘述了，参见解法二

解题

解法一

/**
 * @param {string} start
 * @param {string} end
 * @param {string[]} bank
 * @return {number}
 */
var minMutation = function (start, end, bank) {
  if (start === end) return 0;
  if (bank.indexOf(end) === -1) return -1;
  const n = bank.length;
  let min = 0;
  const bankFlag = new Array(n).fill(0);
  let starts = [start];
  while (starts.length) {
    min++;
    const nexts = [];
    for (let i = 0; i < starts.length; i++) {
      for (let j = 0; j < n; j++) {
        if (bankFlag[j] === 0) {
          let diff = 0;
          for (let k = 0; k < 8; k++) {
            if (starts[i][k] !== bank[j][k]) {
              diff++;
              if (diff > 1) {
                break;
              }
            }
          }
          if (diff === 1) {
            if (bank[j] === end) {
              return min;
            }
            bankFlag[j] = 1;
            nexts.push(bank[j]);
          }
        }
      }
    }
    starts = nexts;
  }
  return -1;
};

解法二

/**
 * @param {string} start
 * @param {string} end
 * @param {string[]} bank
 * @return {number}
 */
var minMutation = function (start, end, bank) {
  const excludes = [];
  const max = bank.length + 1;
  const map = new Map();
  map.set(end, 0);
  const isNext = (curr, next) => {
    let diff = 0;
    for (let j = 0; j < 8; j++) {
      if (curr[j] !== next[j]) {
        diff++;
      }
    }
    return diff === 1;
  };
  const fn = (word) => {
    if (map.has(word)) {
      return map.get(word);
    }
    let count = max;
    for (let i = 0; i < bank.length; i++) {
      if (!excludes.includes(i)) {
        const str = bank[i];
        if (isNext(word, str)) {
          excludes.push(i);
          count = Math.min(count, fn(str) + 1);
          excludes.pop();
        }
      }
    }
    count < max && map.set(word, count);
    return count;
  };
  let count = fn(start);
  return count >= max ? -1 : count;
};