Do not try to traverse a hash set


  • 1
    D

    At first my code is:

    class Solution {
    public:
    	bool isNeighbor(string s1, string s2){
    		string::iterator j = s2.begin();
    		string::iterator i = s1.begin();
    		int cnt = 0;
    		for (; i != s1.end(); ++i, ++j){
    			if (*i != *j){
    				cnt++;
    				if (cnt == 2)
    					return false;
    			}
    		}
    		return true;
    	}
    	int ladderLength(string start, string end, unordered_set<string> &dict) {
    		queue<string> myQueue;
    		string top;
    		unordered_set<string>::iterator temp;
    		int cnt = 0;
    		myQueue.push(start);
    		myQueue.push("");
    		while (myQueue.size() != 1){
    			top = myQueue.front();
    			myQueue.pop();
    			if ("" == top){
    				cnt++;
    				continue;
    				myQueue.push("");
    			}
    			if (isNeighbor(top, end))
    				return cnt + 2;
    			for (unordered_set<string>::iterator iter = dict.begin(); iter != dict.end();){
    				temp = iter;
    				++iter;
    				if (isNeighbor(top, *temp)){
    					myQueue.push(*temp);
    					dict.erase(temp);
    				}
    			}
    
    
    		}
    		return 0;
    	}
    };
    

    I tried to traverse the hash set at first,because I thought it might reduce running time. Actually it cost more time to traverse the hash set, I got a TLE for that code.Then I altered my code,the new one runs 720 ms.

    class Solution {
    public:
    
    	int ladderLength(string start, string end, unordered_set<string> &dict) {
    		dict.erase(start);
    		dict.erase(end);
    		queue<string> myQueue;
    		string top;
    		unordered_set<string>::iterator temp;
    		int cnt = 0;
    		myQueue.push(start);
    		myQueue.push("");
    		while (myQueue.size() != 1){
    			top = myQueue.front();
    			myQueue.pop();
    			if ("" == top){
    				cnt++;
    				myQueue.push("");
    				continue;
    			}		
    			for (int i =0; i <top.size(); ++i){
    				string copy(top);
    				for (char x = 'a'; x <= 'z'; ++x){
    					copy[i] = x;
    					if (copy == end)
    						return cnt + 2;
    					if ((temp = dict.find(copy)) != dict.end()){
    						myQueue.push(*temp);
    						dict.erase(temp);
    					}
    				}
    			}	
    		}
    		return 0;
    	}
    };

  • 0
    M

    I have the same error. Then WHY ?


  • 0
    D

    The elements in a hash set doesn't store in memory consecutively.So it may takes a lot of time to traverse all the elements.


Log in to reply
 

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