https://leetcode.com/problems/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 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.
class Solution {
public:
void dfs(vector<vector<string> >& res, unordered_map<string, vector<string> >& fa, vector<string> load, string beginWord, string curWord) {
if(curWord == beginWord) {
reverse(load.begin(), load.end());
res.push_back(load);
reverse(load.begin(), load.end());
return;
}
for(int i=; i<fa[curWord].size(); ++i) {
load.push_back(fa[curWord][i]);
dfs(res, fa, load, beginWord, fa[curWord][i]);
load.pop_back();
}
}
vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
vector<vector<string> > res;
if(beginWord.compare(endWord) == ) return res;
wordList.insert(endWord);
unordered_map<string, vector<string> > fa;
unordered_set<string> vis;
unordered_set<string> lev;
unordered_set<string> next_lev;
lev.insert(beginWord);
bool found = false;
while(!lev.empty() && !found) {
if(lev.find(endWord) != lev.end()) found = true;
for(auto str: lev) vis.insert(str);
for(auto str : lev) {
for(int i=; i<str.length(); ++i) {
for(char ch = 'a'; ch <= 'z'; ++ch) {
if(str[i] != ch) {
string tmp = str;
tmp[i] = ch;
if(wordList.find(tmp) != wordList.end() && vis.find(tmp) == vis.end()) {
next_lev.insert(tmp);
fa[tmp].push_back(str);
}
}
}
}
}
lev.clear();
swap(lev, next_lev);
}
if(found) {
vector<string> load;
load.push_back(endWord);
dfs(res, fa, load, beginWord, endWord);
}
return res;
}
};