单词接龙

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

每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
sk == endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

示例

这个问题可以使用广度优先搜索（BFS）来解决。首先，我们需要创建一个图来表示单词之间的转换关系。然后，从 beginWord 开始进行 BFS，直到找到 endWord 或者遍历完所有可能的路径。

以下是解决此问题的 JavaScript 代码示例：

function ladderLength(beginWord, endWord, wordList) {const wordSet = new Set(wordList);if (!wordSet.has(endWord)) return 0;const queue = [beginWord];const visited = new Set([beginWord]);let level = 1;while (queue.length > 0) {const size = queue.length;for (let i = 0; i < size; i++) {const currentWord = queue.shift();if (currentWord === endWord) return level;for (let j = 0; j < currentWord.length; j++) {for (let k = 0; k < 26; k++) {const newWord = currentWord.slice(0, j) + String.fromCharCode('a'.charCodeAt(0) + k) + currentWord.slice(j + 1);if (wordSet.has(newWord) && !visited.has(newWord)) {queue.push(newWord);visited.add(newWord);}}}}level++;}return 0;
}// Example usage:
const beginWord = "hit";
const endWord = "cog";
const wordList = ["hot", "dot", "dog", "lot", "log", "cog"];
console.log(ladderLength(beginWord, endWord, wordList)); // Output: 5

在这个代码中，我们首先将 wordList 转换为一个 Set，以便快速检查一个单词是否在 wordList 中。然后，我们使用一个队列来进行 BFS，并使用一个 visited 集合来避免重复访问相同的单词。每次从队列中取出一个单词，我们尝试将其每个位置替换为其他字母，如果得到的新单词在 wordList 中且未被访问过，就将其加入队列。当遇到 endWord 时，返回当前的层级作为最短转换序列的长度。如果遍历完所有可能的路径仍未找到 endWord，则返回 0。

以下是解决此问题的 Python 代码示例：

from collections import defaultdict, dequedef ladderLength(beginWord, endWord, wordList):if endWord not in wordList:return 0# 构建图L = len(beginWord)all_combo_dict = defaultdict(list)for word in wordList:for i in range(L):all_combo_dict[word[:i] + "*" + word[i+1:]].append(word)# 使用队列进行广度优先搜索queue = deque([(beginWord, 1)])visited = set([beginWord])while queue:current_word, level = queue.popleft()for i in range(L):intermediate_word = current_word[:i] + "*" + current_word[i+1:]for word in all_combo_dict[intermediate_word]:if word == endWord:return level + 1if word not in visited:visited.add(word)queue.append((word, level + 1))# 清空当前中间词的所有单词，避免重复访问all_combo_dict[intermediate_word] = []return 0# 示例用法
beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
print(ladderLength(beginWord, endWord, wordList))  # 输出应为 5

我们首先构建了一个字典 all_combo_dict，它将每个单词的所有可能的中间状态映射到与其匹配的其他单词。然后，我们使用一个队列来进行广度优先搜索，同时跟踪当前的层级。当我们找到 endWord 时，返回当前的层级加一（因为我们需要包括 beginWord）。如果遍历完所有可能的路径都没有找到 endWord，则返回 0。