Use BFS and maintain the father node, but got TLE..Can anyone help me? Thank you


  • 0
    H

    I defined a struct to maintain the depth of current bfs node and the father pointer. Once I found the target string(end), I used a temp vector<string>(ans in the program) to get the whole path and push to result. if the depth>shortest depth, break.
    But I got TLE, I don't know how to optimize it;

        class Solution {
    public:
    
        vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
    		vector<vector<string>> result;
    		unordered_set<string> vis;
    		vis.insert(start);
    		queue<DepNode*> q;
    		q.push(new DepNode(start,1,NULL));
    		int predep=0,flag=0,shortPath;
    
    		while(!q.empty()){
    			
    			DepNode* node=q.front();
    			string letter=node->str;
    			int dep=node->dep;
    
    			if(dep>predep)
    			{
    				for(auto it=vis.begin();it!=vis.end();it++)
    				dict.erase(*it);
    			}
    			for(int i=0;i<letter.size();i++)
    			{
    				string tmpstr=letter;
    				for(char c='a';c<='z';c++)
    				{
    					if(tmpstr[i]==c)	continue;
    					tmpstr[i]=c;
    					if(tmpstr==end){
    						if(flag==0)
    						{
    							flag=1;
    							shortPath=dep+1;
    						}
    						else if(dep+1>shortPath)	
    							break;
    						vector<string> ans;
    						ans.push_back(end);
    						DepNode *p=node;
    						while(p!=NULL)
    						{
    							ans.push_back(p->str);
    							p=p->fa;
    						}
    						result.push_back(ans);
    					}
    					else	if(dict.count(tmpstr)>0)
    					{
    						vis.insert(tmpstr);
    						DepNode* pp=new DepNode(tmpstr,dep+1,node);
    						q.push(pp);					
    					}				
    				}			
    			}
    			if(!q.empty())
    			{
    				predep=q.front()->dep;
    				q.pop();
    			}		
    		}
    		for(int i=0;i<result.size();i++)
    			reverse(result[i].begin(),result[i].end());
    		return result;
    }
    
    private:	
    	struct DepNode{
    				string str;
    
    				DepNode *fa;
    
    				int dep;
    
    				DepNode(string s="",int d=0,DepNode *f=NULL){str=s;dep=d;fa=f;}
    			};
    };

Log in to reply
 

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