leetcode-cn.com/problems/mi…

Answer:

  1. Start and end as the starting point, respectively, to advance to the middle, when they meet, that is, to find the shortest path.
  2. Each advance selects the smaller queue at both ends, which can optimize The Times of traversal.
  3. BFS requires the use of queues, which are considered to meet when the next changing word of an element in one queue exists in the queue at the other end.
  4. Using Map to determine if the word is in the queue further optimizes speed. Therefore, the queue on the other end can be converted to a Map each time the queue is traversed.
  5. Test cases to watch out for:
"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) {
  // Use Set to determine if the word in bank has been used
  let bankSet = new Set(bank);

  // If end does not exist in bank, it cannot be changed
  if(! bankSet.has(end)) {return -1;
  }

  // The queue is traversed each time, starting with start, corresponding to level 0
  let queue = [[start, 0]].// Although both traversals need to use queues, Map can be used to speed up the process of checking whether an encounter occurs
  // For each traversal, you only need to take the smaller length of the queue and map and convert it into a queue for traversal
  let map = new Map([[end, 0]]);
  // A variable letter for each gene
  const geneBank = ['A'.'T'.'C'.'G'];

  // If either queue or map is cleared, bidirectional BFS will not meet, that is, conversion cannot be performed
  while (queue.length && map.size) {
    // Select the shorter of the queue and map to traverse to optimize the search speed
    if (queue.length > map.size) {
      // Switch the queue and map to ensure that the queue is traversed each time
      [queue, map] = [Array.from(map), new Map(queue)];
    }

    // Unqueue the elements in the queue and search for the next gene to switch
    const [gene, level] = queue.shift();

    // Iterate over each character of the current gene
    for (let i = 0; i < gene.length; i++) {
      // Select a changeable letter to generate
      for (let j = 0; j < geneBank.length; j++) {
        // If the new letter is the same as the current one, it must not be the next variable gene, so skip it
        if (geneBank[j] === gene[i]) {
          continue;
        }

        // Replace each letter with a new letter to generate a new gene
        const newGene = `${gene.slice(0, i)}${geneBank[j]}${gene.slice(i + 1)}`;

        // If the new gene exists in the Map, it means that the bidirectional BFS encounter, that is, the shortest change path is found
        if (map.has(newGene)) {
          // Add the number of changes at both ends, add the number of changes at the next move to the total number of changes
          return map.get(newGene) + level + 1;
        }

        // If the new gene is in Set, it is the next mutable gene
        if (bankSet.has(newGene)) {
          // Remove it from Set to avoid double selection
          bankSet.delete(newGene);
          // Insert it into the queue for the next change
          queue.push([newGene, level + 1]); }}}}// If the loop is pushed out, no variable path is found and -1 is returned
  return -1;
};
Copy the code