331 ms AC C++ code (along with a question I'm confused about leaving in the comment)


  • 1
    C
    class Solution{
    public:
        vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict){
    		dict.emplace(start);
    		dict.emplace(end);
    		unordered_map<string, vector<string>> from;
    		queue<string> que;
    		que.push(start);
    		dict.erase(start);
    
    		int endLevel = -1;
    		int level = 0;
    		
    		while(!que.empty()){
    			if(endLevel != -1) break;
    			int size = que.size();
    			unordered_set<string> toPush;//this is acctually what the next level is
    			for(int ttt = 0; ttt < size; ttt++){
    				string front = que.front();
    				if(front == end){
    					endLevel = level;
    					break;
    				}
    
    				for(unsigned int i = 0; i < front.size(); i++){
    					string neighbor = front;
    					for(int j = 0; j < 26; j++){
    						neighbor[i] = (char)((int)'a' + j);
    						if(neighbor == front) continue;
    						
    						if((dict.count(neighbor) != 0)){
    							from[neighbor].push_back(front);
    							//very important trick here: keep track of where the neighbor
    							//is from. This will improve the backtrack process since all
    							//the string we trace back from end will lead us back to nothing but start,
    							//we can avoid a lot of unnecessary check here
    							toPush.emplace(neighbor);
    						}
    					}
    				}
    				que.pop();
    			}
    			/*
     * Here is what I don't understand. I firstly use following codes to find neighbors the current string, "front",
     * can "jump" to, by iterating the whole dict. I thought this should be faster than iterating chars in
     * the current string since the iterating the whole dict will take O(dict.size() * each level's size * length of string)
     * while above code takes O(26^length fo string) in time, which should be much greater than the first one.
     * However, I failed with the following case. Can anyone explain the reason, please?
    				string front = que.front();
    				dict.erase(front);
    				if(front == end){
    					endLevel = level;
    					break;
    				}
    				else{
    					for(unordered_set<string>::iterator itr = dict.begin(); itr != dict.end(); itr++){
    						string neighbor = *itr;
    						if(help2(neighbor, front)){
    							from[neighbor].push_back(front);
    							toPush.emplace(neighbor);
    						}
    					}
    				}
    				que.pop();
    			}
    			*/
    
    			level++;
    			for(unordered_set<string>::iterator itr = toPush.begin(); itr != toPush.end(); itr++){
    				string temp = *itr;
    				que.push(temp);
    				dict.erase(temp);
    				//every time after next level is determined, erase them from dict
    				//since they won't be at the next next level(we need to exclude them from the future check)
    			}
    		}
    
    		vector<vector<string>> result;
    		if(from[end].size() == 0) return result;
    		vector<string> tempRes;
    
    		tempRes.push_back(end);
    		help(result, tempRes, endLevel, start, end, from);
    		return result;
        }
    	
    	void help(vector<vector<string>>& result, vector<string>&tempRes, int level, string& start, string& end, unordered_map<string, vector<string>>& from){
    //this is the backtracking function
    //actually level here is not needed since the last word will always be start
    //but I'm just too tired to modify it
    		if(level == 0){
    			vector<string> toPush;
    			for(int i = (int)tempRes.size() - 1; i >= 0; i--){
    				toPush.push_back(tempRes[i]);
    			}
    			result.push_back(toPush);
    
    			return;
    		}
    
    		for(unsigned int i = 0; i < from[end].size(); i++){
    			string neighbor = from[end][i];
    			tempRes.push_back(neighbor);
    			help(result, tempRes, level - 1, start, neighbor, from);
    			tempRes.pop_back();
    		}
    	}
    
    	bool help2(string& s1, string& s2){
    //this is used to see if s1 and s2 are neighbors to each other
    		if(s1.size() != s2.size()) return false;
    		int count = 0;
    		for(unsigned int i = 0; i < s1.size(); i++){
    			if(s1[i] != s2[i]) count++;
    			if(count > 1) return false;
    		}
    		if(count == 0) return false;
    		return true;
    	}
    };

  • 1
    I

    Iterating the whole dict will take a lot of time if the dict is very large while the final function you use is always o(26*len of word). The len of word is much smaller than the dict size. Besides, iterating the whole dict take much more time than you think because it does not store element s in contiguous location.


  • 0
    Q

    I think you were confused that 26^words length will be larger than dictionary size is that you didn't realize that the dictionary may contains words of different length (let's say 10, 26^10 will be extremely large comparing having your own dictionary of 26^3 in this case.)


  • 0
    Q

    I think you were confused that 26^words length will be larger than dictionary size is that you didn't realize that the dictionary may contains words of different length (let's say 10, 26^10 will be extremely large comparing having your own dictionary of 26^3 in this case.)


  • 0
    H

    Here's a 240 ms solution that shares the same idea as yours.

    class Solution {
    public:
    	//int visited;
    	void generatePath(vector<string> &res, vector<vector<string>> &ans, unordered_map<string, vector<string>> &p, int level, string &beginWord, string &word) {
    		//visited++;
    		res.push_back(word);
    		if (level == 1) 
    		{ 
    		    //saved 12 ms
    			vector<string> res1;
    			for (int i = res.size() - 1 ; i >= 0 ; i--) res1.push_back(res[i]);
    			ans.push_back(res1);
    			/*
    			reverse(res.begin(), res.end()); 
    			ans.push_back(res); 
    			reverse(res.begin(), res.end()); 
    			*/
    			
    		} else
    		{
    			for (int i = 0 ; i < p[word].size() ; i++)
    			{
    				generatePath(res, ans, p, level - 1, beginWord, p[word][i]);
    			}
    		}
    		res.pop_back();
    	}
        vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
            vector<vector<string>> ans;
            vector<string> res;
            if (beginWord == endWord) {
                res.push_back(beginWord);
                ans.push_back(res);
                return ans;
            }
            wordList.insert(endWord);
            int k = 0;
            int z = 1;
            int v = 2;  //special
            int u = 1;
            int w = 0;
            vector<string> q;
            unordered_map<string, vector<string>> p;  //parents
            q.push_back(beginWord);
    		wordList.erase(beginWord);
            while (k < z)
            {
                string word = q[k];
                for (auto ch = word.begin() ; ch != word.end() ; ++ch) {
    				char tmp = *ch;
                    for (*ch = 'a' ; *ch <= 'z' ; (*ch)++)
                        if (*ch != tmp) {
                            if (wordList.count(word) > 0) {
    							if (p[word].size() == 0) {
    								q.push_back(word);
    								z++;
    							}
    							p[word].push_back(q[k]);							
                            }
                        }
                    *ch = tmp;
                }
                
                k++;
                if (k >= u) {
    				if (p[endWord].size() > 0) {
    					//visited = 0;					
    					generatePath(res, ans, p, v, beginWord, endWord);
    					//cout<<"Visited: "<<visited<<endl;
    					break;
                    }
    
    				v++;
                    
    				w = u;
                    u = z;
    				for (int j = w ; j < u ; j++) wordList.erase(q[j]);
                }
            }
            return ans;
        }
    };

Log in to reply
 

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