433. 最小基因变化

433. 最小基因变化

leetcode 链接

解法一：倒推 + 递归

从结果 end 倒推

1、如果 bank 中不包含 end,返回 -1；

2、遍历 bank，主要两个操作：

2.1、如果当前字符和 end 相等，并且和 start 相差一位，那么可以直接返回 step + 1（step即递归的次数，递归一次就代表变换了一次，加一即加上当前这一次）；

2.2、找出和 end 相差一位的字符存在新的列表中（newEndList）,并且删除 bank 中和 end 相同的那个字符；

3、遍历 newEndList ，每一项又作为新的 end，重复上述操作（注意：bank 已经去掉了 end），取得计算结果；

4、返回结果（上一步遍历递归计算结果中的最小值 + step）;

/**
 * @param {string} start
 * @param {string} end
 * @param {string[]} bank
 * @return {number}
 */
var minMutation = function (start, end, bank) {
  return getMin(start, end, bank, 0);
};

/**
 * 计算两个字符串相差的位数
 * @return {number}
 */
function notSameCount(str1, str2) {
  let res = 0;
  for (let i = 0; i < 8; i++) {
    if (str1[i] !== str2[i]) {
      res++;
    }
  }
  return res;
}

function getMin(start, end, bank, step) {
  if (!bank.includes(end)) return -1;
  const newEndList = []; // 存储 bank 中和 end 相差一位的字符
  for (let i = 0; i < bank.length; i++) {
    if (bank[i] === end) {
      if (notSameCount(bank[i], start) === 1) {
        // 如果值和 end 相等，并且和 start 相差一位，那么就认为变化完成，返回变化次数
        return step + 1;
      }
      bank.splice(i, 1); // 删除 bank 中和 end 相等的字符，新的 bank 用于下一次递归
      i--; // 删除后 i - 1
    } else if (notSameCount(end, bank[i]) === 1) {
      newEndList.push(bank[i]);
    }
  }
  if (!newEndList.length) return -1; // 如果 bank 中没有和 end 相差一位的，那么就无法完成变化，返回 -1
  const counts = [];
  for (let i of newEndList) {
    const curStep = getMin(start, i, bank, 1); // 把 newEndList 中每一项当做 end 递归
    if (curStep !== -1) {
      counts.push(curStep);
    }
  }
  return Math.min(...counts) + step;
}