c++设计,给两个单词 beginWord 和 endWord 和一个字典 wordList ,返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 0 。 示例 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" 不在字典中,所以无法进行转换。
时间: 2023-07-08 14:51:53 浏览: 38
以下是使用双向 BFS 实现的 C++ 代码:
```c++
#include <vector>
#include <string>
#include <queue>
#include <unordered_set>
#include <unordered_map>
using namespace std;
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> dict(wordList.begin(), wordList.end());
if (dict.find(endWord) == dict.end()) { // endWord 不在字典中
return 0;
}
unordered_set<string> beginSet{beginWord};
unordered_set<string> endSet{endWord};
unordered_set<string> visited;
int step = 1;
while (!beginSet.empty() && !endSet.empty()) {
if (beginSet.size() > endSet.size()) { // 双向 BFS 优化
swap(beginSet, endSet);
}
unordered_set<string> nextLevel;
for (auto word : beginSet) {
for (int i = 0; i < word.size(); i++) {
char oldChar = word[i];
for (char ch = 'a'; ch <= 'z'; ch++) {
word[i] = ch;
if (endSet.find(word) != endSet.end()) { // 相遇
return step + 1;
}
if (visited.find(word) != visited.end() || dict.find(word) == dict.end()) {
continue;
}
nextLevel.insert(word);
visited.insert(word);
}
word[i] = oldChar;
}
}
beginSet = nextLevel;
step++;
}
return 0; // 无法转换
}
```
在上面的代码中,我们使用了 unordered_set 来保存字典和访问过的节点,使用了 unordered_map 来保存节点对应的步数。双向 BFS 优化的原理是,从两端同时进行 BFS,每次选择较小的集合进行扩展,当两个集合相遇时,就找到了最短路径。