给定两个单词(beginWord 和 endWord)和一个字典,找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则:
说明:
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出: 5
解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
返回它的长度 5。
输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出: 0
解释: endWord "cog" 不在字典中,所以无法进行转换。
思路:
特殊情况: 如果字典中不包含endWord则直接返回0
本题可以从两个角度来思考解法:
抛砖引玉
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
var ladderLength = function(beginWord, endWord, wordList) {
if (!wordList.includes(endWord)) return 0
let map = new Map(),
len = wordList.length;
// 记录替换字符后的子集
for (let i = 0; i < len; i++) {
const item = wordList[i],
itemLen = wordList[i].length
for (let j = 0; j < itemLen; j++) {
const newStr = wordList[i].substring(0, j) + '*' + wordList[i].substring(j + 1, itemLen);
if (!map.has(newStr)) map.set(newStr, [])
map.get(newStr).push(wordList[i])
}
}
// 从 beginWord开始枚举可能替换的结果
let queue = [[beginWord, 1]],
visitedMap = new Map([[beginWord, true]]);
while (queue.length) {
let [word, level] = queue.shift(),
itemLen = word.length;
for (let i = 0; i < itemLen; i++) {
const newStr = word.substring(0, i) + '*' + word.substring(i + 1, itemLen);
if (map.has(newStr)) {
for (let j = 0; j < map.get(newStr).length; j++) {
const child = map.get(newStr)[j]
// 遇到endWord终止
if (child === endWord) return level + 1
// 避免重复枚举字符
if (!visitedMap.has(child)) {
visitedMap.set(child, true)
queue.push([child, level + 1]);
}
}
}
}
}
return 0
};
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
var ladderLength = function(beginWord, endWord, wordList) {
let wordSet = new Set(wordList),
queue = [[beginWord, 1]];
while (queue.length) {
let len = queue.length
for (let i = 0; i < len; i++) {
const [word, level] = queue.shift();
if (word == endWord) return level +1
for (let i = 0; i < word.length; i++) {
// 枚举可能存在的转换
for (let c = 1; c <= 26; c++) {
const newWord = word.slice(0, i) + String.fromCharCode(97+c) + word.slice(i + 1)
if (wordSet.has(newWord)) {
queue.push([newWord, level + 1]);
wordSet.delete(newWord);
}
}
}
}
}
return 0
};
注意: 上面广度优先搜索方法转换过程存在顺序,队列尾部的元素依赖队列头部元素先转接,则queue需要遵循队列先进先出原则(FIFO)