127ms C++ Solution


  • 3
    W

    Anyone who has suggestions for further optimization?

    class Solution {
    public:
        vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
            unordered_map<string, vector<vector<string>>> set1, set2, *set_cur, *set_target;
            vector<vector<string>> vec_start(1, vector<string>(1, start)), vec_end(1, vector<string>(1, end));
            //two-end BFS to effectively prune, BFS strategy will get the smaller set to traverse in each iteration
            set1[start] = vec_start;
            set2[end] = vec_end;
            int K = start.size();
            bool isUpdated = true, isFinished = false;
            vector<vector<string>> res;
            for(int depth = 2; isUpdated && !isFinished; ++depth) { 
                if(set1.size() > set2.size()) {
                    set_cur = &set2;
                    set_target = &set1;
                }
                else {
                    set_cur = &set1;
                    set_target = &set2;
                }
                unordered_map<string, vector<vector<string>>> inter_set;
                isUpdated = false;
            unordered_set<string> deleting;
            for(auto iteri=set_cur->cbegin(), end = set_cur->cend(); iteri!=end; ++iteri) {
                for(int i=0; i<K; ++i) {
                    string temp = (*iteri).first;
                    char ch = 'a';
                    for(int c = 0; c<26; ++c) {
                        temp[i] = ch + c;
                        if(set_target->find(temp) != set_target->end()) {
                            const vector<vector<string>> *new_paths_first = &(*iteri).second;
                            const vector<vector<string>> *new_paths_second = &(*set_target)[temp];
                            auto iter_in = set_cur->cbegin();
                            if(((*iter_in).second)[0][0] != start) {
                                new_paths_first = &(*set_target)[temp];
                                new_paths_second = &(*iteri).second;  
                            }   
                            for_each(new_paths_first->cbegin(), new_paths_first->end(), [&] (const vector<string> &first_path) {
                                    for_each(new_paths_second->cbegin(), new_paths_second->cend(), [&] (const vector<string> &second_path) {
                                        vector<string> temp_path = first_path;
                                        for_each(second_path.crbegin(), second_path.crend(), [&](const string &s) {
                                            temp_path.push_back(s);
                                            }); 
                                        res.push_back(temp_path);
                                        }); 
                                    }); 
                            isFinished = true;
                        }   
                        else if(dict.find(temp) != dict.end()) {
                            vector<vector<string>> new_paths = (*iteri).second;
                            for_each(new_paths.begin(), new_paths.end(), [&] (vector<string> &path) {
                                    path.push_back(temp);
                                    }); 
                            if(inter_set.find(temp) == inter_set.end())
                                inter_set[temp] = new_paths;
                            else {
                                for_each(new_paths.begin(), new_paths.end(), [&] (vector<string> &path) {
                                        inter_set[temp].push_back(path);
                                        }); 
                            }   
                            deleting.insert(temp);
                            isUpdated = true;
                        }   
                    }   
                }   
            }   
            for_each(deleting.begin(), deleting.end(), [&] (const string &s) {
                        dict.erase(s);
                    }); 
                *set_cur = inter_set;
            }
            return res;
        }
    };

  • 0
    J

    impressive. super fast!!


  • 0

    Here is my 88ms solution use two-end BFS:

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

Log in to reply
 

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