## # 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:

1. Only one letter can be changed at a time
2. 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.

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)
{
}
}
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;