127. 单词接龙
127. 单词接龙
🔴 🔖 广度优先搜索
哈希表
字符串
🔗 力扣
LeetCode
题目
A transformation sequence from word beginWord
to word endWord
using a dictionary wordList
is a sequence of words beginWord -> s1 -> s2 -> ... -> sk
such that:
- Every adjacent pair of words differs by a single letter.
- Every
si
for1 <= i <= k
is inwordList
. Note thatbeginWord
does not need to be inwordList
. sk == endWord
Given two words, beginWord
and endWord
, and a dictionary wordList
, return the number of words in the shortest transformation sequence from beginWord
to endWord
, or0
if no such sequence exists.
Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.
Example 2:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.
Constraints:
1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord
,endWord
, andwordList[i]
consist of lowercase English letters.beginWord != endWord
- All the words in
wordList
are unique.
题目大意
字典 wordList
中从单词 beginWord
到 endWord
的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk
:
- 每一对相邻的单词只差一个字母。
- 对于
1 <= i <= k
时,每个si
都在wordList
中。注意,beginWord
不需要在wordList
中。 sk == endWord
给你两个单词 beginWord
和 endWord
和一个字典 wordList
,返回 从 beginWord
到 endWord
的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 0
。
解题思路
这道题和 433 最小基因变化 很像,可以转换为 图的最短路径问题,每个单词是图中的节点,两个只相差一个字母的单词之间有一条边。因此可以使用 广度优先搜索(BFS) 来求解。
只不过第 433 题给定了基因的变化范围是 A/T/G/C
,而这道题中,用于替换单词中每个字符的字符范围需要自己从 wordList
中求得。
- 将起始单词
beginWord
放入队列queue
,同时设定一个集合visited
用于记录已经访问过的单词,避免重复访问。 - 每次从队列中取出一个单词,尝试将其每个字符替换,看看是否能得到一个新的有效单词(这个新单词需要在字典中存在,且没有被访问过)。
- 如果某次得到的单词等于目标单词
endWord
,直接返回当前的变化次数step + 1
。 - 如果该单词有效且未访问,则将其加入队列,继续下一步的遍历。
- 如果队列为空但还未找到目标单词,返回
0
,表示无法到达目标单词。
复杂度分析
- 时间复杂度:
O(n / m)
,其中n
是字典中的单词数量,m
是单词的长度。在每次 BFS 扩展时,我们会对每个单词的每个字母进行替换,生成新的单词并检查是否存在于字典中。 - 空间复杂度:
O(k * m + n)
,其中n
是字典中的单词数量,m
是单词的长度,k
是用于替换单词中每个字符的字符范围,最大为26
。
代码
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
var ladderLength = function (beginWord, endWord, wordList) {
// 将 wordList 转化为 Set 便于快速查找
const wordSet = new Set(wordList);
// 用于计算替换单词中每个字符的字符范围
const charSet = new Array(beginWord.length)
.fill(0)
.map((_, i) => new Set(wordList.map((item) => item[i])));
if (!wordSet.has(endWord)) return 0;
// 初始化队列
let queue = [beginWord],
visited = new Set([beginWord]),
step = 0;
// BFS 搜索
while (queue.length) {
const len = queue.length;
for (let i = 0; i < len; i++) {
var cur = queue.shift();
// 如果找到目标单词,返回步数 + 1
if (cur == endWord) {
return step + 1;
}
// 尝试改变每个字符
for (let newWord of getAllDiff(cur, charSet)) {
// 如果新的单词在 wordSet 中且还没访问过
if (!visited.has(newWord) && wordSet.has(newWord)) {
// 加入队列中,并标记已访问
queue.push(newWord);
visited.add(newWord);
}
}
}
// 步数 +1
step++;
}
return 0;
};
// 用于计算替换单词中每个字符的所有可能结果
var getAllDiff = function (word, charSet) {
let res = new Set();
chars = word.split('');
for (let i = 0; i < word.length; i++) {
let char = word[i];
for (let newChar of charSet[i]) {
chars[i] = newChar;
res.add(chars.join(''));
}
chars[i] = char;
}
return [...res];
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
126 | 单词接龙 II | 广度优先搜索 哈希表 字符串 1+ | ||
433 | 最小基因变化 | [✓] | 广度优先搜索 哈希表 字符串 | |
2452 | 距离字典两次编辑以内的单词 | 数组 字符串 |