Using BFS and backtracking but still got MLE


  • 0
    L

    idea is to using BFS and build an unordered_map to store all the possible previous words for each word. and then backtracking based on this unordered_map. Got an MLE.. Appreciate it if someone can help!

    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) 
    {
    	if (dict.find(start)!=dict.end())
    	{
    		dict.erase(start);
    	}
    	vector<vector<string>> result;
    	queue<string> q;
    	q.push(start);
    	unordered_map<string,vector<string>> prev_paths;//store the prev words for the key			
    	dict.insert(end);	
    	bool found_the_end = false;
    	int q_size = 0;
    	vector<string> per_level;	
    	int level = 0;
    	int i = 0;		
    	string q_top;
    	string t;
    	while (1)
    	{
    		int unvisited_leaf_num = 0;
    		q_size = q.size();
    		i = 0;
    		per_level.clear();
    		q_top.clear();
    		while ((i<q_size))
    		{
    			q_top = q.front();
    			if (q_top == end) //found the end
    			{
    				found_the_end = true;
    				break;
    			}
    			string t = q_top;
    			for (int k = 0; k<q_top.size();k++)
    			{
    				t = q_top;
    				for (char d1 = 'a'; d1<='z';d1++)
    				{
    					if (q_top[k]!=d1)
    					{
    						t[k] = d1;
    						if (dict.find(t)!=dict.end())
    						{						
    							unvisited_leaf_num++;
    							q.push(t);									
    							prev_paths[t].push_back(q_top);
    							per_level.push_back(t);
    						}
    					}
    				}
    			}			
    			q.pop();			
    			i++;
    		}		
    		//delete per level to enable duplication at each level
    		for (int j = 0; j<per_level.size();j++)
    		{			
    			dict.erase(per_level[j]);
    		}
    		//if end appears in per_level
    		level++;
    		if (found_the_end)
    		{
    			break;
    		}
    		//if all words have been visited, but still not found the end, return
    		if (unvisited_leaf_num==0)
    		{
    			return result;
    		}
    	}	
    	//trace back through prev_paths
    	int level_counter = 1;	
    	vector<string> tmp;
    	tmp.push_back(end);
    	result.push_back(tmp);
    	while (level_counter<level)
    	{
    		int cur_result_size = result.size();
    		for (int j = 0; j<cur_result_size; j++)
    		{
    			result[j].insert(result[j].begin(),prev_paths[result[j][0]][0]);
    			for (int k = 0; k<prev_paths[result[j][1]].size()-1;k++)
    			{
    				result.push_back(result[j]);
    				result.back().front() = prev_paths[result[j][1]][k+1];
    			}
    		}
    		level_counter++;
    	}	
    	prev_paths.clear();
    	per_level.clear();
    	tmp.clear();
    	return result;
    }

Log in to reply
 

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