Original link: leetcode-cn.com/problems/wo…

Answer:

  1. The traversal is done using queues, in which the elements of each layer are stored in order.
  2. Each time through the loop, the elements of the current layer in the queue are taken one by one, and words that change only once are searched in the wordList as elements for the next layer to traverse and placed in the queue.
  3. Store all the wordList elements in a Set, and remove each used word from the Set to avoid repeated queries.
  4. Since BFS traverses layer by layer, once a word is equal to the target word, it can exit the loop in order to find the minimum number of changes.
  5. Test cases to watch out for:
"ymain"
"oecij"
["ymann","yycrj","oecij","ymcnj","yzcrj","yycij","xecij","yecij","ymanj","yzcnj","ymain"]
Copy the code
/ * * *@param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}* /
var ladderLength = function (beginWord, endWord, wordList) {
  let queue = [beginWord]; // Stores the starting word in the queue to start the loop
  // Store the wordList as a Set and delete the passed words in the traversal to reduce unnecessary traversal
  let wordSet = new Set(wordList); // 
  // You need to return the length of the converted word, beginWord is also counted, so the initial length is 1
  let count = 1;

  // Use queues for BFS
  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) {
      // Retrieves a word from the current queue to find a word that is one letter away from it
      let str = queue.shift();

      // Find the word in Set,
      for (const word of wordSet) {
        let diff = 0; // Count the number of letters that differ by one

        // Iterate over each letter and compare the number of changes
        for (let i = 0; i < word.length; i++) {
          // If the number of letters changes, count
          if(str[i] ! == word[i]) { diff++;// If the difference is more than one letter, it is not an option for this change and exits the loop
            if (diff > 1) {
              break; }}}// When a letter changes by one, select the current word as the change path
        if (diff === 1) {
          // If the current change is consistent with the target, return the current path length
          if (word === endWord) {
            return count + 1;
          }
          // Remove the currently selected word from Set to avoid double selection
          wordSet.delete(word);
          // Queues the current word for the next loopqueue.push(word); }}}// For each layer traversal, increment the path length by one
    count++;
  }

  // If the loop does not exit, the path was not found and 0 is returned
  return 0;
};
Copy the code