原文：127. 单词接龙(leetcode 解题) - 每天一个JavaScript小知识@Js中文网 · 码农进阶题库

原文地址：https://www.javascriptc.com/interview-tips/zh_cn/leetcode/leetcode-javascript-solution-0127/

题目：

难度：Middle

相关话题：广度优先搜索

给定两个单词（beginWord 和 endWord ）和一个字典，找到从beginWord 到endWord 的最短转换序列的长度。转换需遵循如下规则：

  1. 每次转换只能改变一个字母。

  2. 转换过程中的中间单词必须是字典中的单词。

说明:

  • 如果不存在这样的转换序列，返回 0。

  • 所有单词具有相同的长度。

  • 所有单词只由小写字母组成。

  • 字典中不存在重复的单词。

  • 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

示例1:

输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

输出:5

解释:一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
     返回它的长度 5。

示例 2:

输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

输出:0

解释:endWord "cog" 不在字典中，所以无法进行转换。

思路：

BFS。

思路一：

首先将startWord添加到arr中，对arr内部的每个字符串，从wordList找出与它只相差1个字母的字符串，添加到arr中。

思路二：

同样将startWord添加到arr中，对arr内部的每个字符串的每个字母，不断替换它为另外的其他25个字母， 然后查看hash(wordList)中是否存在，如果存在，添加到arr并且删除当前字符串的hash，因为不需要再次使用。

注意：

思路一的缺陷就是如果wordList过大，相对的每次查找相差1字母的时间也同样增加；

思路二不需要考虑wordList的长度，但它的缺陷在于每一个字符都要替换26次，因此如果每一个字符串的长度过长，同样会出现性能问题。

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */
var ladderLength = function(beginWord, endWord, wordList) {
  // bfs
  // if(!wordList.includes(endWord))return 0
  // wordList.push(beginWord)
  // let steps=Array(wordList.length).fill(Infinity)
  // let arr=[endWord],aux=[]
  // let stepCount=0
  // while(arr.length>0){
  //   stepCount++
  //   for(let i=0;i<arr.length;i++){
  //     let cur=arr[i]
  //     for(let j=0;j<wordList.length;j++){
  //       if(cur===wordList[j])continue
  //       let res=checkSteps(cur,wordList[j])
  //       if(res && steps[j]>1){
  //         if(wordList[j]===beginWord)return stepCount+1
  //         aux.push(wordList[j])
  //         steps[j]=1
  //       }
  //     }
  //   }
  //   arr=aux
  //   aux=[]
  // }
  // return 0
  // function checkSteps(s1,s2){
  //   let diff=0
  //   for(let i=0;i<s1.length;i++){
  //     if(s1[i]!==s2[i])diff++
  //     if(diff>1)return false
  //   }
  //   return true
  // }

  // bfs2
  let hash=new Map()
  for(let word of wordList)hash.set(word,true)
  if(!hash.has(endWord))return 0
  let arr=[beginWord]
  let step=0
  while(arr.length>0){
    step++
    let len=arr.length
    for(let i=0;i<len;i++){
      let cur=arr.shift()
      let newStr=''
      for(let j=0;j<cur.length;j++){
        let l=cur.substring(0,j),r=cur.substring(j+1)
        for(let k=0;k<26;k++){
          newStr=l+String.fromCharCode(k+97)+r
          if(hash.has(newStr)){
            if(newStr===endWord)return step+1
            arr.push(newStr)
            hash.delete(newStr)
          }
        }
      }
    }
  }
  return 0
};

扩展阅读：