跳至主要內容

127. 单词接龙


127. 单词接龙open in new window

🔴   🔖  广度优先搜索 哈希表 字符串  🔗 力扣open in new window LeetCodeopen in new window

题目

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 for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
  • 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, and wordList[i] consist of lowercase English letters.
  • beginWord != endWord
  • All the words in wordList are unique.

题目大意

字典 wordList 中从单词 beginWordendWord转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk

  • 每一对相邻的单词只差一个字母。
  • 对于 1 <= i <= k 时,每个 si 都在 wordList 中。注意, beginWord 不需要在 wordList 中。
  • sk == endWord

给你两个单词 beginWordendWord 和一个字典 wordList ,返回 从 beginWordendWord最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 0

解题思路

这道题和 433 最小基因变化 很像,可以转换为 图的最短路径问题,每个单词是图中的节点,两个只相差一个字母的单词之间有一条边。因此可以使用 广度优先搜索(BFS) 来求解。

只不过第 433 题给定了基因的变化范围是 A/T/G/C,而这道题中,用于替换单词中每个字符的字符范围需要自己从 wordList 中求得。

  1. 将起始单词 beginWord 放入队列 queue,同时设定一个集合 visited 用于记录已经访问过的单词,避免重复访问。
  2. 每次从队列中取出一个单词,尝试将其每个字符替换,看看是否能得到一个新的有效单词(这个新单词需要在字典中存在,且没有被访问过)。
  3. 如果某次得到的单词等于目标单词 endWord,直接返回当前的变化次数 step + 1
  4. 如果该单词有效且未访问,则将其加入队列,继续下一步的遍历。
  5. 如果队列为空但还未找到目标单词,返回 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单词接龙 IIopen in new window广度优先搜索 哈希表 字符串 1+
433最小基因变化open in new window[✓]广度优先搜索 哈希表 字符串
2452距离字典两次编辑以内的单词open in new window数组 字符串