433.最小基因变化

433.最小基因变化

Category	Difficulty	Likes	Dislikes
algorithms	Medium (53.49%)	166	-

Tags
Companies
基因序列可以表示为一条由 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’] 组成

---

Discussion | Solution

思路

数据量不打，暴力模拟可解。从 end 开始，dfs 比较每一种可能，如果一条路线能够回到 start，那么计算线路长度并更新结果，最后返回结果即可。

解答

/*
 * @lc app=leetcode.cn id=433 lang=javascript
 *
 * [433] 最小基因变化
 */

// @lc code=start
/**
 * @param {string} start
 * @param {string} end
 * @param {string[]} bank
 * @return {number}
 */
var minMutation = function (start, end, bank) {
  const compare = (str1, str2) => {
    if (str1.length !== str2.length) return false;
    let flag = true;
    for (let i = 0; i < str1.length; i++) {
      const char1 = str1[i],
        char2 = str2[i];
      if (char1 !== char2) {
        if (flag) {
          flag = false;
          continue;
        }
        return false;
      }
    }
    return true;
  };

  let flag = Infinity;

  const dfs = (str, arr, count) => {
    if (!arr.length) return;
    if (compare(start, str)) {
      flag = Math.min(count + 1, flag);
      return;
    }
    for (let i = 0; i < arr.length; i++) {
      const str1 = arr[i];
      if (compare(str1, str)) {
        dfs(str1, [...arr.slice(0, i), ...arr.slice(i + 1)], count + 1);
      }
    }
  };

  if (!bank.includes(end)) return -1;

  dfs(end, bank, 0);

  return flag === Infinity ? -1 : flag;
};
// @lc code=end