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


  • 1

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

Log in to reply
 

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