Word Ladder II

Q:

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.

T:
Do level by level BFS. Do not add a word in a new level if it already appears in previous levels. To do this, we can simple erase the words in the current level from the dictionary before processing next level. We also need a set for each word to remember its previous words to generate the paths when finally reaching the end.

A:

class Solution {
public:
    vector< vector< string> > findLadders(string start, string end, unordered_set &dict) {
        vector< vector< string > > ret;
        if(start.size() != end.size()) {
            return ret;
        }
        unordered_set< string > qu;
        qu.insert(start);
        dict.erase(start);
        vector< string > v;
        v.push_back(start);
        if(start == end) {
            ret.push_back(v);
            return ret;
        }
        unordered_map< string, unordered_set< string > > previous;
        while(!qu.empty()) {
            unordered_set< string > oldqu(qu);
            qu.clear();
            if(oldqu.find(end) != qu.end()) {
                bool stop = false;
                vector< string > vec;
                vec.push_back(end);
                ret.push_back(vec);
                while(!stop) {
                    stop = true;
                    int sz = ret.size();
                    for(int i=0; i< sz; i++) {
                        string cur = ret[i][0];
                        vector< string > tmp = ret[i];
                        tmp.insert(tmp.begin(), "");
                        unordered_set< string > & pres = previous[cur];
                        for( auto pre : pres) {
                            if(stop && pre != start) {
                                stop = false;
                            }
                            tmp[0] = pre;
                            ret.push_back(tmp);
                        }
                    }
                    for(int i=0; i< sz; i++) {
                        ret.erase(ret.begin());
                    }
                }
                break;
            }
            for(auto str : oldqu) {
                for(int i=0; i< str.size(); i++) {
                    for(char c='a'; c<= 'z'; c++) {
                        if(c != str[i]) {
                            string newstr = str;
                            newstr[i] = c;
                            if(dict.find(newstr) != dict.end() || newstr == end) {
                                previous[newstr].insert(str);
                                qu.insert(newstr);
                            }
                        }
                    }
                }
            }
            for( auto visited : qu) {
                dict.erase(visited);
            }
        }
        return ret;
    }
};