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

• 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;}
};
};``````

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