126. 单词接龙 II
本文共 1791 字，大约阅读时间需要 5 分钟。
为了解决从 beginWord 到 endWord 的最短转换序列问题，我们可以使用广度优先搜索（BFS）来找到所有可能的最短路径。每次转换只能改变一个字母，并且中间单词必须在给定的字典中。
方法思路
预处理：首先，检查所有单词的长度是否一致。如果不一致，直接返回空列表。 构建字典映射：使用哈希表（字典）存储单词及其对应的位置，以便快速查找。 BFS初始化：从 beginWord 开始，加入队列，并记录为已访问。 BFS遍历：在每一步中，生成所有可能的变换单词（每个字母都可以变成其他25个字母），并检查这些变换是否在字典中且未被访问过。如果是，将它们加入队列。 记录路径：当找到 endWord 时，记录路径并继续搜索，直到队列为空，确保找到所有可能的最短路径。 解决代码
#include #include #include #include using namespace std;vector > findLadders(string beginWord, string endWord, vector wordList) { int n = beginWord.size(); // 检查所有单词长度是否一致 for (const string& word : wordList) { if (word.size() != n) { return {}; } } unordered_map wordId; for (int i = 0; i < wordList.size(); ++i) { wordId[wordList[i]] = i; } // 检查beginWord和endWord是否在字典中 if (wordId.find(beginWord) == wordId.end() || wordId.find(endWord) == wordId.end()) { return {}; } queue > q; unordered_set visited; vector > result; q.push({beginWord, 0}); visited.insert(beginWord); while (!q.empty()) { auto current = q.front(); q.pop(); string currentWord = current.first; int steps = current.second; if (currentWord == endWord) { result.push_back({currentWord}); continue; // 继续搜索可能的其他路径 } for (int i = 0; i < currentWord.size(); ++i) { char c = currentWord[i]; for (char ch = 'a'; ch <= 'z'; ++ch) { if (ch == c) continue; string newWord = currentWord; newWord[i] = ch; // 检查新单词是否在字典中且未被访问过 if (wordId.find(newWord) != wordId.end() && !visited.count(newWord)) { visited.insert(newWord); q.push({newWord, steps + 1}); } } } } return result;}
代码解释
预处理：检查所有单词的长度是否一致，确保转换过程中的单词长度保持一致。 字典映射：使用 unordered_map 记录每个单词的位置，以便快速查找。 BFS初始化：从 beginWord 开始，初始化队列和已访问集合。 BFS遍历：生成所有可能的变换单词，检查是否在字典中，未被访问过，并加入队列。 路径记录：每当找到 endWord 时，记录路径并继续搜索，确保找到所有可能的最短路径。 这样，BFS算法能够高效地找到所有最短转换序列，确保中间单词都在字典中。
转载地址：http://rcnpz.baihongyu.com/