leetCode Question Word Ladder II

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

(1)  Breadth First Search is a better way than the DFS for this problem.

(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 be calculated and saved.

(3) We need to output the exact path, so we need to store the paths.

(4) For each words in the BFS queue, we still need to  to generate the valid words in the dicts (from 1st to last, change every char from ‘a’ to ‘z’ ).findDict2 function below implements it.

(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 this level.

(6) 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.

(7) 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.

Code:

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.compare(start) == 0){
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)!=next_lev.end()){ //if find end string
output(start,end);
return res;
}

cur_lev.clear();
cur_lev = next_lev;
next_lev.clear();
}
return res;
}

Best alternative solution:

Preprocess the dictionary in form of graph. Create an edge between two words only if it can be reached by changing one letter. Now the problem reduces to apply bfs/dfs to reach from source to destination.