My 1300ms C++ solution, BFS. How to improve it?


  • 1
    B

    Is there any other way to improve the solution , except using "a-z" to erase the dict?

    class Solution {
    private:
    	bool similar(const string &a, const string&b)
    	{
    		if (a.length() == 0 || b.length() == 0)
    		{
    			return false;
    		}
    		int counter = 0;
    		for (int i = 0; i < a.length(); i++)
    		{
    			if (a[i] != b[i])
    			{
    				counter++;
    				if (counter>1)
    					return false;
    			}
    		}
    		return true;
    	}
    public:
    	int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) {
    		if (beginWord==endWord)
    		{
    			return 1;
    		}
    		pair<string, int> temp;
    		queue<pair<string, int>> G;
    		G.push(pair<string, int>(beginWord, 1));
    		int findL =0;
    		while (!G.empty())
    		{
    			temp = G.front(); G.pop();
    			if (similar(temp.first, endWord))
    			{
    				findL = temp.second + 1;
    				return findL;
    			}
    			for (unordered_set<string>::iterator it = wordDict.begin(); it != wordDict.end(); )
    			{
    				if (similar(*it, temp.first)  )
    				{
    					G.push(pair<string, int>(*it,temp.second+1));
    					unordered_set<string>::iterator it1 = it;
    					it++;
    					wordDict.erase(it1);
    					continue;
    				}
    				it++;
    			}
    		}
    		return findL;
    	}
    };

  • 0
    B

    This is a 300ms version. But I'm looking for some other way.

    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) {
    		if (beginWord==endWord)
    		{
    			return 1;
    		}
    		pair<string, int> temp;
    		queue<pair<string, int>> G;
    		G.push(pair<string, int>(beginWord, 1));
    		int findL =0;
    		while (!G.empty())
    		{
    			temp = G.front(); G.pop();
    			for (int i = 0; i < temp.first.length();i++)
    			{
    				char c2=temp.first[i];
    				for (char c1 = 'a'; c1 <= 'z';c1++)
    				{
    					if (c1 != temp.first[i])
    					{
    						temp.first[i] = c1;
    						if (temp.first==endWord)
    						{
    							return temp.second + 1;
    						}
    						if (wordDict.find(temp.first)!=wordDict.end())
    						{
    							G.push(pair<string, int>(temp.first, temp.second + 1));
    							wordDict.erase(temp.first);
    						}
    					}
    					temp.first[i] = c2;
    				}
    			}
    		}
    		return findL;
    	}

Log in to reply
 

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