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:

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;    
    }
};

5 comments:

  1. why not using "queue" for cur_lev and next_lev instead of unordered_set?

    ReplyDelete
    Replies
    1. To avoid duplicated element traversed multiple times. That's why this solution doesn't exceed the time limit.

      Delete
  2. Hi, I want to why store the parents for each word instead of its children? I tried to store a word' children using a map. But it gets MLE.

    ReplyDelete
  3. What I did was first got the minLength by using Word Ladder 1 method. Then used recursion to get all the words of pathLength equal to minLength. It passed all the test cases. You can check my dfs function for implimantation below

    http://ide.geeksforgeeks.org/4X3enD

    ReplyDelete