字典 wordList 中从单词 beginWord 到 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：
- 每一对相邻的单词只差一个字母。
- 对于
1 <= i <= k时，每个si都在wordList中。注意，beginWord不需要在wordList中。 sk == endWord
给你两个单词 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" 不在字典中，所以无法进行转换。
思路：
-
使用
unordered_set存储字典： 查找效率高，O(1)。 -
使用
unordered_map记录访问状态和路径长度：-
防止重复访问（剪枝）
-
存路径长度用于返回答案
-
-
每个字符位都尝试替换成 a-z：
-
用
j + 'a'生成新的字符
-
-
BFS 一层一层搜索，最先到达
endStr的路径就是最短路径。
它其实是边遍历边构建图：
-
每个单词的“邻居”就是所有只差一个字母的合法单词；
-
而这些邻居不是预先计算的，而是实时根据
wordSet和字母替换来动态判断的。
你可以理解为：
图没显式地建出来，但你每次“替换一个字母”其实就是在 隐式地找相邻节点。
代码如下：
class Solution {
public:
int ladderLength(string beginWord, string endWord,
vector<string>& wordList) {
// 字典转换为set，方便查询
unordered_set<string> strSet;
for (int i = 0; i < wordList.size(); i++) {
strSet.insert(wordList[i]);
}
if (strSet.find(endWord) == strSet.end()) {
return 0;
}
// 记录strSet里字符串是否被访问过，同时记录路径长度
unordered_map<string, int> visitedMap;
queue<string> que;
que.push(beginWord);
visitedMap.insert({beginWord, 1});
while (!que.empty()) {
string curword = que.front();
que.pop();
int path = visitedMap[curword];
for (int i = 0; i < curword.size(); i++) {
string newword = curword;
for (int j = 0; j < 26; j++) {
newword[i] = 'a' + j;
if (newword == endWord) {
return path + 1;
}
if (strSet.find(newword) != strSet.end() &&
visitedMap.find(newword) == visitedMap.end()) {
visitedMap.insert({newword, path + 1});
que.push(newword);
}
}
}
}
return 0;
}
};
暂无评论