Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
- Only one letter can be changed at a time
- Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:
- Return an empty list if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
- You may assume no duplicates in the word list.
- You may assume beginWord and endWord are non-empty and are not the same.
Example 1:
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"] Output:
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Example 2:
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"] Output: [] Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
个人感觉这道题是相当有难度的一道题，它比之前那道 Word Ladder 要复杂很多，全场第四低的通过率 12.9% 正说明了这道题的难度，博主也是研究了网上别人的解法很久才看懂，然后照葫芦画瓢的写了出来，下面这种解法的核心思想是 BFS，大概思路如下：目的是找出所有的路径，这里建立一个路径集 paths，用以保存所有路径，然后是起始路径p，在p中先把起始单词放进去。然后定义两个整型变量 level，和 minLevel，其中 level 是记录循环中当前路径的长度，minLevel 是记录最短路径的长度，这样的好处是，如果某条路径的长度超过了已有的最短路径的长度，那么舍弃，这样会提高运行速度，相当于一种剪枝。还要定义一个 HashSet 变量 words，用来记录已经循环过的路径中的词，然后就是 BFS 的核心了，循环路径集 paths 里的内容，取出队首路径，如果该路径长度大于 level，说明字典中的有些词已经存入路径了，如果在路径中重复出现，则肯定不是最短路径，所以需要在字典中将这些词删去，然后将 words 清空，对循环对剪枝处理。然后取出当前路径的最后一个词，对每个字母进行替换并在字典中查找是否存在替换后的新词，这个过程在之前那道 Word Ladder 里面也有。如果替换后的新词在字典中存在，将其加入 words 中，并在原有路径的基础上加上这个新词生成一条新路径，如果这个新词就是结束词，则此新路径为一条完整的路径，加入结果中，并更新 minLevel，若不是结束词，则将新路径加入路径集中继续循环。写了这么多，不知道你看晕了没有，还是看代码吧，这个最有效：
class Solution {
public:
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
vector<vector<string>> res;
unordered_set<string> dict(wordList.begin(), wordList.end());
vector<string> p{beginWord};
queue<vector<string>> paths;
paths.push(p);
int level = , minLevel = INT_MAX;
unordered_set<string> words;
while (!paths.empty()) {
auto t = paths.front(); paths.pop();
if (t.size() > level) {
for (string w : words) dict.erase(w);
words.clear();
level = t.size();
if (level > minLevel) break;
}
string last = t.back();
for (int i = ; i < last.size(); ++i) {
string newLast = last;
for (char ch = 'a'; ch <= 'z'; ++ch) {
newLast[i] = ch;
if (!dict.count(newLast)) continue;
words.insert(newLast);
vector<string> nextPath = t;
nextPath.push_back(newLast);
if (newLast == endWord) {
res.push_back(nextPath);
minLevel = level;
} else paths.push(nextPath);
}
}
}
return res;
}
};
Github 同步地址：
https://github.com/grandyang/leetcode/issues/126
类似题目：
参考资料：
https://leetcode.com/problems/word-ladder-ii/
http://yucoding.blogspot.com/2014/01/leetcode-question-word-ladder-ii.html
https://leetcode.com/problems/word-ladder-ii/discuss/40487/Java-Solution-with-Iteration