88ms! Accepted c++ solution with two-end BFS. 68ms for Word Ladder and 88ms for Word Ladder II


  • 34

    In order to reduce the running time, we should use two-end BFS to slove the problem.

    Accepted 68ms c++ solution for Word Ladder.

    class Solution {
    public:
        int ladderLength(std::string beginWord, std::string endWord, std::unordered_set<std::string> &dict) {
    		if (beginWord == endWord)
    			return 1;
            std::unordered_set<std::string> words1, words2;
    		words1.insert(beginWord);
    		words2.insert(endWord);
            dict.erase(beginWord);
            dict.erase(endWord);
            return ladderLengthHelper(words1, words2, dict, 1);
        }
    
    private:
        int ladderLengthHelper(std::unordered_set<std::string> &words1, std::unordered_set<std::string> &words2, std::unordered_set<std::string> &dict, int level) {
    		if (words1.empty())
                return 0;
    		if (words1.size() > words2.size())
    			return ladderLengthHelper(words2, words1, dict, level);
            std::unordered_set<std::string> words3;
            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())
                                return level + 1;
    						else if (dict.find(word) != dict.end()) {
                                dict.erase(word);
                                words3.insert(word);
                            }
    				*ch = tmp;
                }
            }
            return ladderLengthHelper(words2, words3, dict, level + 1);
        }
    };
    

    Accepted 88ms c++ solution for Word Ladder II.

    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 || findLaddersHelper(words2, words3, dict, nexts, words1IsBegin);
        }
    	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();
    			}
    	}
    };
    

  • 1

    if (*ch != tmp) is unnecessary since you have erased that word in dict.


  • 14

    Hi, prime_tang. Thanks for your two-end BFS code. It is really fast!

    I have rewritten your code below. I hope it is Ok.

    class Solution {
    public:
        vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
            vector<vector<string> > ladders;
            vector<string> ladder;
            ladder.push_back(start);
            unordered_set<string> startWords, endWords;
            startWords.insert(start);
            endWords.insert(end);
            unordered_map<string, vector<string> > children;
            bool flip = true;
            if (searchLadders(startWords, endWords, dict, children, flip))
                genLadders(start, end, children, ladder, ladders);
            return ladders;
        }
    private:
        bool searchLadders(unordered_set<string>& startWords, unordered_set<string>& endWords, 
                     unordered_set<string>& dict, unordered_map<string, vector<string> >& children, bool flip) {
            flip = !flip;
            if (startWords.empty()) return false;
            if (startWords.size() > endWords.size())
                return searchLadders(endWords, startWords, dict, children, flip);
            for (string word : startWords) dict.erase(word);
            for (string word : endWords) dict.erase(word);
            unordered_set<string> intermediate;
            bool done = false;
            for (string word : startWords) {
                int n = word.length();
                string temp = word;
                for (int p = 0; p < n; p++) {
                    char letter = word[p];
                    for (int i = 0; i < 26; i++) {
                        word[p] = 'a' + i;
                        if (endWords.find(word) != endWords.end()) {
                            done = true;
    						flip ? children[word].push_back(temp) : children[temp].push_back(word);
                        }
                        else if (!done && dict.find(word) != dict.end()) {
                            intermediate.insert(word);
    						flip ? children[word].push_back(temp) : children[temp].push_back(word);
                        }
                    }   
                    word[p] = letter;
                }
            }
            return done || searchLadders(endWords, intermediate, dict, children, flip);
        }
        void genLadders(string& start, string& end, unordered_map<string, vector<string> >& children, 
                        vector<string>& ladder, vector<vector<string> >& ladders) {
            if (start == end) {
                ladders.push_back(ladder);
                return;
            }
            for (string child : children[start]) {
                ladder.push_back(child);
                genLadders(child, end, children, ladder, ladders);
                ladder.pop_back();
            }
        }
    };

  • 0

    Hi, jianchao.li.fighter, thanks!


  • 0

    Thanks for your reminder that if (*ch != tmp) is unnecessary !


  • 0

    Hi, prime_tang. Your code is really fast! :-)


  • 0
    R

    explain your ideas than just copy pasting


  • 0

    The logic of this problem is not complicated, I think we can try to read the code and understand it by oneself. Therefore, I did not provide detailed explanation, but noted that it is a two-end BFS solution. Happy try! Just like jianchao.li.fighter does!


  • -1
    R

    I found a better cleaner solution


  • 4
    P

    I rewrite it so no recursion is needed!

    bool buildNexts(string start, string end, unordered_set<string> &dict, map<string,vector<string>> &nexts) {
        unordered_set<string> head{start}, tail{end};
        int len = start.size();
        bool headIsFront = true, found = false;
        while (!head.empty() && !tail.empty()) {
            if (head.size() > tail.size()) {
                swap(head,tail);
                headIsFront = !headIsFront;
            }
            unordered_set<string> tmp;
            for (auto word: head) {
                dict.erase(word);
                string headWord = word;
                for (int i = 0;i < len;++i) {
                    char letter = word[i];
                    for (int j = 'a';j <= 'z';++j) {
                        word[i] = j;
                        if (tail.find(word) != tail.end()) {
                            headIsFront ? nexts[headWord].push_back(word) : nexts[word].push_back(headWord);
                            found = true;
                        } else if (!found && dict.find(word) != dict.end()) {
                            headIsFront ? nexts[headWord].push_back(word) : nexts[word].push_back(headWord);
                            tmp.insert(word);
                        }
                    }
                    word[i] = letter;
                }
            }
            if (found) return true;
            for (auto word: tmp) // it's important to delete words here, but no other places!
                dict.erase(word);
            head = tmp;
        }
        return false;
    }
    
    void buildAns(string start, string end, map<string,vector<string>> &nexts, vector<string> &path, vector<vector<string>> &ans) {
        if (start == end) {
            ans.push_back(path);
            return;
        }
        for (auto s :nexts[start]) {
            path.push_back(s);
            buildAns(s, end, nexts, path, ans);
            path.pop_back();
        }
    }
    
    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
        vector<vector<string>> ans;
        vector<string> path(1, start);;
        map<string,vector<string>> nexts;
        if (buildNexts(start,end,dict,nexts))
            buildAns(start,end,nexts,path,ans);
        return ans;
    }

  • 0
    J

    Is there any way that don't need to change dictionary?


  • 0
    E

    What are you checking with bool words1IsBegin?


  • 0
    J

    I find some tricky place.In fact this solution uses some feature of compiler, because if you reverse the order of "return done || searchLadders(endWords, intermediate, dict, children, flip);" into "return searchLadders(endWords, intermediate, dict, children, flip) || done;", it will generate some extra "correct" but longer path, which don't satisfy the "shortest path" request of the problem.
    I think using this compiler's feature to avoid unnecessary further recursion is so clever! Thanks for sharing, code for fun ;)


  • 1

    @JulianWang12 That's simply because || will shortcut the right hand side if the left hand side is already true.


  • 0
    N

    Why we are using flip variable ?


  • 0
    A

    Actually, the "dict.erase(word);" after for is not needed,it will be executed only twice in the process, just earse beginword and endword


  • 0
    B

    Hi Jianchao,

    May I ask how your algo handles the "collision" case, which means that at one level, 2 words will grow the the same word in the next level, like "mark" and "part" both go to "park" in the next level?

    In this case, doesn't the "part" have 2 paths?

    When I tackled this question, I used an unordered_map<string, vector<list<string))) (cpp) to store the paths. It beats 70% of answers, but still not concise enough.

    Thanks for your help!


  • 0
    B

    man, that's so cool


Log in to reply
 

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