# 126. Word Ladder II
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.
# Solution
Approach 1: First BFS to get the shortest path length, and then DFS to get all shortest paths.
# Code (Python)
Approach 1:
# Code (C++)
Approach 1:
// First BFS to get the shortest path length, and then DFS to get all shortest paths.
class Solution {
private:
unordered_map<string,vector<string>> umap;
vector<vector<string>> res;
bool isTransformable(string a, string b) {
if (a.size() != b.size())
return false;
int count = 0;
for (int i = 0; i < a.size(); ++i)
{
if (a[i] != b[i])
count++;
if (count > 1)
break;
}
return count == 1;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
bool visited[wordList.size()] = {false};
queue<string> q;
q.push(beginWord);
int level = 1;
bool found = false;
while (!q.empty() && !found)
{
level++;
int qSize = q.size();
unordered_set<int> buf;
for (int i = 0; i < qSize; ++i)
{
string curr = q.front();
q.pop();
for (int j = 0; j < wordList.size(); ++j)
{
if (!visited[j] && isTransformable(curr, wordList[j]))
{
if (!found && wordList[j] == endWord)
found = true;
buf.insert(j);
umap[curr].push_back(wordList[j]);
}
}
}
for (unordered_set<int>::iterator it = buf.begin(); it != buf.end(); ++it)
{
visited[*it] = true;
q.push(wordList[*it]);
}
}
return (found) ? level : 0;
}
void doFindLadders(string beginWord, string endWord, vector<string>& wordList, vector<string>& buf, int level) {
buf.push_back(beginWord);
if (beginWord == endWord)
{
res.push_back(buf);
buf.pop_back();
return;
}
if (level > 1)
{
for (int i = 0; i < umap[beginWord].size(); ++i)
{
doFindLadders(umap[beginWord][i], endWord, wordList, buf, level-1);
}
}
buf.pop_back();
}
public:
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
// Remove beginWord from wordList to avoid the infinit loop.
for (int i = 0; i < wordList.size(); ++i)
{
if (wordList[i] == beginWord)
{
wordList.erase(wordList.begin() + i);
break;
}
}
int len = ladderLength(beginWord, endWord, wordList);
vector<string> buf;
doFindLadders(beginWord, endWord, wordList, buf, len);
return res;
}
};