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:

  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.
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;
}
};
04-15 07:01