Difficulty: Hard

Frequency: N/A

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 intermediate word must exist in the word list

For example,

Given:
beginWord = `"hit"`
endWord = `"cog"`
wordList = `["hot","dot","dog","lot","log"]`

Return

```  [
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
```

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
```class Solution {
public:
vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
m.clear();
results.clear();
path.clear();

wordList.insert(beginWord);
wordList.insert(endWord);

unordered_set<string> cur_lev;
cur_lev.insert(beginWord);
unordered_set<string> next_lev;
path.push_back(endWord);

while (true) {
// delete previous level words
for (auto it = cur_lev.begin(); it != cur_lev.end(); it++) {
wordList.erase(*it);
}
// find current level words
for (auto it = cur_lev.begin(); it != cur_lev.end(); it++) {
findDict(*it, wordList, next_lev);
}
if (next_lev.empty()) {
return results;
}
// if find endWord
if (next_lev.find(endWord) != wordList.end()) {
output(beginWord, endWord);
return results;
}
cur_lev.clear();
cur_lev = next_lev;
next_lev.clear();
}
return results;
}
private:
unordered_map<string, vector<string>> m;
vector<vector<string>> results;
vector<string> path;
void findDict(string word, unordered_set<string>& wordList, unordered_set<string>& next_level) {
int n = word.size();
string s = word;
for (int i = 0; i < n; i++) {
s = word;
for (int j = 0; j < 26; j++) {
s[i] = 'a' + j;
if (wordList.find(s) != wordList.end()) {
next_level.insert(s);
m[s].push_back(word);
}
}
}
}
void output(string& start, string last) {
if (last == start) {
reverse(path.begin(), path.end());
results.push_back(path);
reverse(path.begin(), path.end());
} else {
for (int i = 0; i < m[last].size(); i++) {
path.push_back(m[last][i]);
output(start, m[last][i]);
path.pop_back();
}
}
}
};
```

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn:

## 2 thoughts on “126. Word Ladder II”

1. […]  Word Ladder II […]

Like