题目描述
难度:Middle
相关话题:广度优先搜索
给定两个单词(beginWord 和 endWord )和一个字典,找到从beginWord 到endWord 的最短转换序列的长度。转换需遵循如下规则:
- 每次转换只能改变一个字母。
-
转换过程中的中间单词必须是字典中的单词。
说明:
- 如果不存在这样的转换序列,返回 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
};
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com