Share my c++ solution.Can I improve it?


  • 0
    C
    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) {
    	if(beginWord.size() == 0 || endWord.size() == 0)
    		return 0;
    	queue<string> queue;
    	queue.push(beginWord);
    	string flag = "";
    	queue.push(flag);
    	int count = 1;
    
    	while(!queue.empty()){
    		string word = queue.front();
    		queue.pop();
    		if(word.compare(endWord) == 0)
    			return count;
    		if(word.compare(flag) == 0 && queue.back().compare(flag) != 0){
    			count++;
    			queue.push(flag);
    			continue;
    		}
    		for(int i = 0;i<word.length();i++){
    			for(char c = 'a';c<'z';c++){
    				string s = word;
    				s[i] = c;
    				if(wordDict.find(s) != wordDict.end()){
    					queue.push(s);
    					wordDict.erase(s);
    				}
    			}
    		}
    	}
        return 0;
    }

  • 0
    Z

    try two-end method.

    it will also use bfs, but you can taverse the path from the start node and the end node instead of just from the begining. it may save a lot of time.

    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) {
    unordered_set<string> beginSet, endSet, *set1, *set2;
    int res = 1;
    beginSet.insert(beginWord);
    endSet.insert(endWord);
    while (!beginSet.empty() && !endSet.empty())
    {
    	if (beginSet.size() <= endSet.size())
    	{
    		set1 = &beginSet;
    		set2 = &endSet;
    	}
    	else
    	{
    		set1 = &endSet;
    		set2 = &beginSet;
    	}
    	++res;
    	unordered_set<string>tmp;
    	for (auto cur : *set1)
    	{
    		string tmpcur = cur;
    		for (auto &i : tmpcur)
    		{
    			char c = i;
    			for (auto j = 0; j < 26; ++j)
    			{
    				i = j + 'a';
    				if (set2->find(tmpcur) != set2->end())
    					return res;
    				if (wordDict.find(tmpcur) != wordDict.end())
    				{
    					tmp.insert(tmpcur);
    					wordDict.erase(tmpcur);
    				}
    			}
    			i = c;
    			//tmpcur = cur; //it's seems like the oj's optimization will ignore this satement and read the register.
    		}
    	}
    	swap(tmp, *set1);
    }
    return 0;
    

    }


Log in to reply
 

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