Simple solution using level order traversal and recursion


#1

vector<vector > all;
vector curr;
void recur(map<string,vector > parents,string start,string endin){
if(endin==start){
curr.push_back(start);
vector temp = curr;
reverse(temp.begin(),temp.end());
if(find(all.begin(),all.end(),temp)==all.end())all.push_back(temp);
curr.pop_back();
return;
}
curr.push_back(endin);
for(auto s:parents[endin]){
recur(parents,start,s);
}
curr.pop_back();
return;
}
vector<vector > Solution::findLadders(string start, string end, vector &dict) {
string endin = end;
all.clear();
curr.clear();
dict.push_back(endin);
map<string,bool> is_visited;
for(auto s:dict){
is_visited[s] = false;
}
map<string,vector > parent;
deque dq;
dq.push_back(start);
parent[start].push_back("");
bool found = false;
while(!dq.empty() && !found){
int siz = dq.size();
vector all_children;
while(siz–){
bool fd2 = false;
string dis = dq.front();
dq.pop_front();
int m = dis.size();
for(int i=0;i<m;i++){
string temp = dis;
for(char j=‘a’;j<=‘z’;j++){
temp[i] = j;
if(temp==endin){
fd2 = true;
}
if(is_visited.find(temp)!=is_visited.end() && is_visited[temp]==false){
//cout << temp << endl;
all_children.push_back(temp);
dq.push_back(temp);
parent[temp].push_back(dis);
}
if(fd2)break;
}
if(fd2)break;
}
if(fd2)found = true;
}
for(auto s:all_children){
is_visited[s]=true;
}
}
recur(parent,start,endin);
return all;
}