leetcode-cn.com/problems/mi…

Answer:

  1. A. the b. the C. the D. the
    • Find the minimum number of gene changes from start to end from bank.
    • Genes can only change one character at a time.
    • The path of change is not unique.
  2. Using DFS:
    • For each recursion, the gene that changes only one character compared with the current gene is selected from the bank and taken as the intermediate result to enter the lower recursion.
    • To ensure that elements in bank are not selected repeatedly, Set is used to identify whether elements in bank have been accessed.
    • If the intermediate result is equal to end, a possible change path is found.
    • Since there is more than one path, minimize the number of changes.
  3. Important cases:
"AACCGGTT"
"AAACGGTA"
["AACCGATT","AACCGATA","AAACGATA","AAACGGTA"]
Copy the code
"AAAACCCC"
"CCCCCCCC"
["AAAACCCA","AAACCCCA","AACCCCCA","AACCCCCC","ACCCCCCC","CCCCCCCC","AAACCCCC","AACCCCCC"]
Copy the code
/ * * *@param {string} start
 * @param {string} end
 * @param {string[]} bank
 * @return {number}* /
var minMutation = function (start, end, bank) {
  let used = new Set(a);// Indicate whether the bank has been accessed
  let min = Infinity; // Store the result, default is Infinity, to avoid the error of taking the minimum value

  // Use DFS to find all possible paths to change
  function dfs(
    str, // The intermediate result of each gene change
    count, // Number of gene changes
  ) {
    // Recursive termination condition
    // When a gene changes to a target, the number of changes has been found
    if (str === end) {
      // Since you can find many variations, you need a minimum
      min = Math.min(count, min);
      return;
    }

    // The current level recurses logic
    // Since the possible change path will be randomly selected in the bank, the bank will be traversed from 0 each time
    for (let i = 0; i < bank.length; i++) {
      // If the current value has already been used, continue to match the next value
      if (used.has(bank[i])) {
        continue;
      }

      let diff = 0; // Count the difference between STR and bank[I], with a value of 1 indicating a possible change

      // Iterate over each character of bank[I]
      for (let j = 0; j < bank[i].length; j++) {
        // If STR is inconsistent with bank[I], count the number of gene changes
        if(str[j] ! == bank[i][j]) { diff++;// If the difference is greater than 1, the bank[I] is not a possible change, exit the loop
          if (diff > 1) {
            break; }}}// Enter the lower level recursion
      // The gene can only change one character at a time, so a diff of 1 is required to enter the next level of recursion
      if (diff === 1) {
        // Indicates that bank[I] has been used
        used.add(bank[i]);
        Bank [I] = bank[I] = bank[I] = bank[I] = bank[I
        dfs(bank[i], count + 1);
        // Clear the current recursive state
        // Clear the bank[I] usage state for the next for loopused.delete(bank[i]); }}}// Start DFS search from the initial gene sequence, the initial number of changes is 0
  dfs(start, 0);

  // If min is Infinity, no result is found, return -1, otherwise return min
  return min === Infinity ? -1 : min;
};
Copy the code