I used backtracking, but got a TLE, don't know Why??


  • 1
    P
    class Solution {
    public:
        vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
    		auto it = dict.begin();
    		while(it != dict.end()) {
    			if(*it == start || *it == end) it = dict.erase(it);
    			else {
    				(MyHash[*it])++;
    				it++;	
    			}
    		}
    		minLength = 0; pre = start; temp.push_back(start);
    		help(start, end, dict);
    		return Result;
        }
    private:
        vector<vector<string> > Result; 
    	vector<string> temp;
    	unordered_map<string, int> MyHash;
    	string pre;
    	int minLength;
    	
    	void help(string start, string end, unordered_set<string> &dict) {
    		for(auto it = dict.begin(); it != dict.end(); it++) {
    			if(OneWordDiff(*it, pre) && MyHash[*it] > 0) {
    				string tempPre = pre;
    				pre = *it;
    				(MyHash[pre])--;
    				temp.push_back(pre);
    				if(OneWordDiff(pre, end)) {
    					temp.push_back(end);
    					if(minLength == 0) {
    						Result.push_back(temp);
    						minLength = temp.size();
    					}
    					else {
    						if( temp.size() < minLength ) {
    							Result.clear();
    							Result.push_back(temp);
    							minLength = temp.size();
    						} else if( temp.size() == minLength ){
    							Result.push_back(temp);
    						}
    					}
    					temp.pop_back();
    				}
    				else {
    					help(start, end, dict);
    				}
    				(MyHash[pre])++;
    				temp.pop_back();	
    				pre = tempPre;
    			}
    		}
    	}
    	
    	bool OneWordDiff(string s1, string s2) {
    		int count = 0;
    		for(int i=0; i<s1.length(); i++) {
    			if(s1[i] != s2[i]) count++;
    			if(count > 1) return false;
    		}
    		return true;
    	}
    };

  • 0
    P

    when the dict is very large, it's terrible to do with traversing the dict every recursion.


Log in to reply
 

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