leetCode Question Word Ladder II

leetCode Question Word Ladder II

Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary
For example,
Given:
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:

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

Resolving technical problems:

Solve your technical problems instantly

We provide Remote Technical Support from Monday to Sunday, 7:00PM to 1:00 AM

Mail your problem details at writeulearn@gmail.com along with your mobile numberand we will give you a call for further details. We usually attend your problems within 60 minutes and solve it in maximum 2 days.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.