Word Ladder II
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the dictionary
For example,
Given:
start =
end =
dict =
start =
"hit"end =
"cog"dict =
["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.
Analysis:
This is NOT an easy problem because of the time and memory requirements.(1) From the previous Word Ladder I, we know that Breadth First Search is a better way than the DFS.
(2) The requirement of this question is to output ALL the shortest path, which means if we find one path using the BFS, then all the other shortest paths must also in this level, so the search will stop once this level ends.
(3) We need to output the exact path, so we need one way to store the paths.
(4) For each words in the BFS queue, we still need to use the previous way to generate the valid words in the dicts (from 1st to last, change every char from 'a' to 'z' ).
(5) Duplicates is permitted within a level. e.g.,
hem -> hex -> tex -> ted
hem-> tem -> tex -> ted, are all valid paths.
Draw this into a tree structure:
hem
/ \
hex tem
| |
tex tex
| |
ted ted
A solution is to erase all the words in the previous level, instead of erasing words for each word in the level.
(6) Some experiences that I tried and failed:
(a). Use a big map to store valid words for each dict(map<string, vector<string> >). Failed: Memory Limit Exceeds.
(b). Use the struct as Word Ladder I, add one "pre" string member to store the path. Failed: Memory Limit Exceeds.
(c). Use a vector to store the path. Failed: either time limit exceeds, or failed to track all the paths.
(d). Use bidirectional BFS. Failed: complex to track all the paths.
(7) Use a map to store and retrieve the paths. map<string, vector<string> >, stores all the previous strings for current string. Retrieval of the path will need recursion.
(8) Because we have the map storing the paths, the standard queue is not needed. Because what we do now is searching each level (see the tree above), once we found the path, still need to finish that level and apply the output. So two "queue" can be used, one stores the current level words, one stores the next level words. The next level words are generated from the current level. During the generation of valid words, path can be stored at the same time. When the next level words are all generated, if the end string is included, we can output the paths, otherwise, we can erase the words in current level, and search the next level. This erasing step is helping reduce the dict, and eliminate the case that a cycle exists in the path.
(9) The dict in the last test case contains about 3,000 words.
Code:
class Solution {
public:
unordered_map<string,vector<string> > mp; // result map
vector<vector<string> > res;
vector<string> path;
void findDict2(string str, unordered_set<string> &dict,unordered_set<string> &next_lev){
int sz = str.size();
string s = str;
for (int i=0;i<sz;i++){
s = str;
for (char j = 'a'; j<='z'; j++){
s[i]=j;
if (dict.find(s)!=dict.end()){
next_lev.insert(s);
mp[s].push_back(str);
}
}
}
}
void output(string &start,string last){
if (last==start){
reverse(path.begin(),path.end());
res.push_back(path);
reverse(path.begin(),path.end());
}else{
for (int i=0;i<mp[last].size();i++){
path.push_back(mp[last][i]);
output(start,mp[last][i]);
path.pop_back();
}
}
}
vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
mp.clear();
res.clear();
path.clear();
dict.insert(start);
dict.insert(end);
unordered_set<string> cur_lev;
cur_lev.insert(start);
unordered_set<string> next_lev;
path.push_back(end);
while (true){
for (auto it = cur_lev.begin();it!=cur_lev.end();it++){dict.erase(*it);} //delete previous level words
for (auto it = cur_lev.begin();it!=cur_lev.end();it++){ //find current level words
findDict2(*it,dict,next_lev);
}
if (next_lev.empty()){return res;}
if (next_lev.find(end)!=dict.end()){ //if find end string
output(start,end);
return res;
}
cur_lev.clear();
cur_lev = next_lev;
next_lev.clear();
}
return res;
}
};
