给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord em> 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典中的单词。
说明:
- 如果不存在这样的转换序列，返回 0。
- 所有单词具有相同的长度。
- 所有单词只由小写字母组成。
- 字典中不存在重复的单词。
- 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 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" 不在字典中，所以无法进行转换。
解法一：
//时间复杂度O(m*n), 空间复杂度O(m*n)
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_map<string, vector<string>> um;
for(string& word : wordList) {
for(int i = 0; i < word.size(); i++) {
string temp = word.substr(0, i) + "*" + word.substr(i + 1);
um[temp].push_back(word);
}
}
int res = 1;
unordered_set<string> visited;
queue<string> q1, q2;
q1.push(beginWord);
while(!q1.empty()) {
q1.swap(q2);
while(!q2.empty()) {
string cur = q2.front();
q2.pop();
if(cur == endWord) return res;
visited.insert(cur);
for(int i = 0; i < cur.size(); i++) {
string temp = cur.substr(0, i) + "*" + cur.substr(i + 1);
if(um.count(temp)) {
for(string& s : um[temp]) {
if(visited.count(s)) continue;
q1.push(s);
}
}
}
}
res++;
}
return 0;
}
};解法一：
BFS。步骤如下：
- 使用一个哈希表保存wordList中所有单词，其key为可能的模式，value为符合对应模式的单词列表，例如 {"a*c" : { abc, adc, aec } }。对于wordList中的词可以组成一个无向图，每个单词可看作一个结点，符合相同模式的两个单词可认为共用一条边；
- 以beginWord为出发点，对该图进行层序搜索，每深入一层，对计数值res加1；
- 直到cur == endWord时返回res，或者遍历完所有路径返回0。
2019/12/01 22:17