博客

1 题目

给定两个单词（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” 不在字典中，所以无法进行转换。

2 思路

这道题开始考察图的遍历，首先建立图结构，连接具有相同字母的单词，建立

allWords

，

key

为某种种形式，例如

*ot

，

value

为具有该形式的单词列表，例如

hot、dot、lot

，这样就可以快速得到指定形式的单词，随后从

beginWord

开始广度遍历整个图，当找到

endWord

时，表明得到了转换路径

3代码

/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */
var ladderLength = function(beginWord, endWord, wordList) {
    if (!wordList.includes(endWord)) return 0;

    let len = beginWord.length;
    const allWords = {};

    for (let word of wordList) {    //遍历每个单词，建立图
        for (let i=1; i<=len; i++) {
            let key = `${word.slice(0,i-1)}*${word.slice(i,len)}`;
            if (!allWords[key])  allWords[key] = [];
            allWords[key].push(word);
        }
    }

    const quque = [{word: beginWord, index: 1}];   //index用于记录走了多少步
    const visited = {};

    while(quque.length > 0) {    //广度优先遍历整个图
        let item = quque.shift();
        for (let i=1; i<=len; i++) {
            let key = `${item.word.slice(0,i-1)}*${item.word.slice(i,len)}`;
            if (!allWords[key]) continue;
            for (let j=0; j<allWords[key].length; j++) {
                let word = allWords[key][j]
                if (word === endWord) return item.index + 1;
                if (visited[word]) continue;
                quque.push({word, index: item.index + 1});
                visited[word] = true;
            }
        }
    }

    return 0;
};