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. Use BFS:
    • Use Set to save genes in the bank and delete them if they have been used before to avoid double selection.
    • The traversal is done using queues, in which the elements of each layer are stored in order.
    • In each cycle, the elements of the current layer in the queue are removed one by one, and all possible genetic changes are generated.
    • If the newly generated gene is in the Set, it indicates that it is the next change, and it is queued and deleted from the Set.
    • Since BFS traverses layer by layer, once a sequence is equal to the target sequence, it can exit the loop in order to find the minimum number of changes.
  3. Important cases:
"AACCGGTT"
"AACCGGTA"
[]
Copy the code
"AACCGGTT"
"AAACGGTA"
["AACCGATT","AACCGATA","AAACGATA","AAACGGTA"]
Copy the code
"AAAACCCC"
"CCCCCCCC"
["AAAACCCA","AAACCCCA","AACCCCCA","AACCCCCC","ACCCCCCC","CCCCCCCC","AAACCCCC","AACCCCCC"]
Copy the code
"AAAAAAAA"
"CCCCCCCC"
["AAAAAAAA","AAAAAAAC","AAAAAACC","AAAAACCC","AAAACCCC","AACACCCC","ACCACCCC","ACCCCCCC","CCCCCCCA"]
Copy the code
/ * * *@param {string} start
 * @param {string} end
 * @param {string[]} bank
 * @return {number}* /
var minMutation = function (start, end, bank) {
  let level = 0; // Count the depth of BFS traversal
  let queue = [start]; // Stores the initial gene sequence in the queue, which is used to start the cycle
  let bankSet = new Set(bank); // Store unaccessed gene sequences
  let charBank = ['A'.'T'.'C'.'G']; // A variable letter for each gene

  // Complete BFS by iterating through the queue until it is empty
  while (queue.length) {
    // Cache the number of elements in the current queue, i.e. the number of elements in the current layer
    let queueLength = queue.length;

    // Perform queueLength traversal
    while (--queueLength >= 0) {
      // Unqueue the current gene in the queue
      const currGene = queue.pop();

      // Iterate over the letters of the current gene
      for (let i = 0; i < currGene.length; i++) {
        // Find an available letter from the currently changeable letter
        for (let j = 0; j < charBank.length; j++) {
          // Avoid generating sequences that duplicate the current gene
          if (charBank[j] === currGene[i]) {
            continue;
          }

          // Generate a new gene sequence
          const newGene = `${currGene.slice(0, i)}${ charBank[j] }${currGene.slice(i + 1)}`;

          // Determine whether the new gene is used
          if (bankSet.has(newGene)) {
            // If the new gene is found to be the same as the target for the first time, the shortest change path has been found
            if (newGene === end) {
              // Since the current change is not counted, increment is required to return the result
              return ++level;
            }

            // Delete the current gene from Set, indicating that it has been accessed
            bankSet.delete(newGene);
            // Store the current gene in the array for the next changequeue.push(newGene); }}}}// After each layer traversal, the number of changes increases by 1
    level++;
  }

  // If you exit the loop, the change path is not found and -1 is returned
  return -1;
};
Copy the code