A concise solution using bfs and backtracing


  • 11
    S

    the basic idea is referred from url: http://yucoding.blogspot.com/2014/01/leetcode-question-word-ladder-ii.html

    unordered_map<string, vector<string> > mp; // a map indicating a word's previous word list
    vector<vector<string> > res;
    vector<string> path;
     
    void output(string &start, string last) {
        if (last == start) {
            // vector<string> t(path.rbegin(), path.rend());
            // res.push_back(t);
            reverse(path.begin(), path.end());
            res.push_back(path);
            reverse(path.begin(), path.end());
        }
        else {
            // backtracing to get path recursively
            for (int i = 0; i < mp[last].size(); ++i) {
                path.push_back(mp[last][i]);
                output(start, mp[last][i]);
                path.pop_back();
            }
        }
    }
    
    void findNext(string str, unordered_set<string> &dict, unordered_set<string> &next_lev) {
        for (int i = 0; i < str.size(); ++i) {
            string s = str;
            for (char j = 'a'; j <= 'z'; ++j) {
                s[i] = j;
                if (dict.count(s)) {
                    next_lev.insert(s);
                    mp[s].push_back(str);
                }
            }
        }
    }
    
    vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) {
        unordered_set<string> cur_lev;
        cur_lev.insert(start);
        unordered_set<string> next_lev;
        path.push_back(end);
         
        // expand to get all the next level valid words
        while (true) {
            for (auto it = cur_lev.begin(); it != cur_lev.end(); it++)
                dict.erase(*it); //delete previous level words from dict to avoid the cycle
             
            for (auto it = cur_lev.begin(); it != cur_lev.end(); it++)
                findNext(*it, dict, next_lev); //find current level words
             
            if (next_lev.empty()) return res;
            
            if (next_lev.count(end)) { //if find end string
                output(start, end);
                return res;
            }
            
            cur_lev = next_lev;
            next_lev.clear();
        }
        
        return res;    
    }

  • 0
    S

    The blog is very helpful.


  • 2

    Your code can not work when the end word is not in the dictionary, so I think you should insert dict.insert(end); before the while loop! If not, for

    start = "hit"
    end = "cog"
    dict = ["hot","dot","dog","lot","log"]
    

    you will get nothing.

    In fact, for this problem, use two-end BFS is a better idea, here is my 88ms c++ solution:

    class Solution {
    public:
        std::vector<std::vector<std::string> > findLadders(std::string beginWord, std::string endWord, std::unordered_set<std::string> &dict) {
            std::vector<std::vector<std::string> > paths;
            std::vector<std::string> path(1, beginWord);
            if (beginWord == endWord) {
                paths.push_back(path);
                return paths;
            }
            std::unordered_set<std::string> words1, words2;
            words1.insert(beginWord);
            words2.insert(endWord);
            std::unordered_map<std::string, std::vector<std::string> > nexts;
            bool words1IsBegin = false;
            if (findLaddersHelper(words1, words2, dict, nexts, words1IsBegin))
                getPath(beginWord, endWord, nexts, path, paths);
            return paths;
        }
    private:
        bool findLaddersHelper(
            std::unordered_set<std::string> &words1,
            std::unordered_set<std::string> &words2,
            std::unordered_set<std::string> &dict,
            std::unordered_map<std::string, std::vector<std::string> > &nexts,
            bool &words1IsBegin) {
            words1IsBegin = !words1IsBegin;
            if (words1.empty())
                return false;
            if (words1.size() > words2.size())
                return findLaddersHelper(words2, words1, dict, nexts, words1IsBegin);
            for (auto it = words1.begin(); it != words1.end(); ++it)
                dict.erase(*it);
            for (auto it = words2.begin(); it != words2.end(); ++it)
                dict.erase(*it);
            std::unordered_set<std::string> words3;
            bool reach = false;
            for (auto it = words1.begin(); it != words1.end(); ++it) {
                std::string word = *it;
                for (auto ch = word.begin(); ch != word.end(); ++ch) {
                    char tmp = *ch;
                    for (*ch = 'a'; *ch <= 'z'; ++(*ch))
                        if (*ch != tmp)
                            if (words2.find(word) != words2.end()) {
                                reach = true;
                                words1IsBegin ? nexts[*it].push_back(word) : nexts[word].push_back(*it);
                            }
                            else if (!reach && dict.find(word) != dict.end()) {
                                words3.insert(word);
                                words1IsBegin ? nexts[*it].push_back(word) : nexts[word].push_back(*it);
                            }
                    *ch = tmp;
                }
            }
            return reach ? true : findLaddersHelper(words2, words3, dict, nexts, words1IsBegin);
        }
    private:
        void getPath(
            std::string beginWord,
            std::string &endWord,
            std::unordered_map<std::string, std::vector<std::string> > &nexts,
            std::vector<std::string> &path,
            std::vector<std::vector<std::string> > &paths) {
            if (beginWord == endWord)
                paths.push_back(path);
            else
                for (auto it = nexts[beginWord].begin(); it != nexts[beginWord].end(); ++it) {
                    path.push_back(*it);
                    getPath(*it, endWord, nexts, path, paths);
                    path.pop_back();
                }
        }
    };

  • 2

    Hi, shichaotan. Thank you for your sharing. I have understood the code and reorganized it a little bit below.

    class Solution {
    public:
        vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
            dict.insert(start);
            dict.insert(end);
            unordered_set<string> current;
            unordered_set<string> next;
            current.insert(start);
            ladder.push_back(end);
            while (true) {
                for (string cur : current)
                    dict.erase(cur);
                for (string cur : current)
                    findChildren(cur, next, dict);
                if (next.empty()) return ladders;
                if (next.find(end) != next.end()) {
                    genLadders(start, end);
                    return ladders;
                } 
                current.clear();
                swap(current, next);
            }
        }
    private:
        unordered_map<string, vector<string> > ancestors;
        vector<string> ladder;
        vector<vector<string> > ladders;
        
        void findChildren(string& word, unordered_set<string>& next, unordered_set<string>& dict) {
            int n = word.length();
            string ancestor = word;
            for (int p = 0; p < n; p++) {
                char letter = word[p];
                for (int i = 0; i < 26; i++) {
                    word[p] = 'a' + i;
                    if (dict.find(word) != dict.end()) {
                        next.insert(word);
                        ancestors[word].push_back(ancestor);
                    }
                }
                word[p] = letter;
            }
        }
        void genLadders(string& start, string& end) {
            if (start == end) {
                reverse(ladder.begin(), ladder.end());
                ladders.push_back(ladder);
                reverse(ladder.begin(), ladder.end());
                return;
            }
            for (string ancestor : ancestors[end]) {
                ladder.push_back(ancestor);
                genLadders(start, ancestor);
                ladder.pop_back();
            }
        }
    };

  • 0

    How do you sure the end is in dict?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.