BFS+Backtracking Easy Solution


#1

void fun(unordered_map<string,int> &mp,string cur,string des,vector<vector > &ans,vector tem){
if(cur==des){
tem.push_back(des);
ans.push_back(tem);
return;
}
tem.push_back(cur);
int v=mp[cur];
for(int i=0;i<cur.size();i++){
for(int j=0;j<26;j++){
char t=cur[i];
cur[i]=j+‘a’;
if(mp.find(cur)!=mp.end()){
if((mp[cur]+1)==v){
fun(mp,cur,des,ans,tem);
}
}
cur[i]=t;
}
}
}
vector<vector > Solution::findLadders(string A, string B, vector &C) {
queue que;
que.push(A);
int ans=0;
unordered_map<string,int> mp;
for(auto c:C){
mp[c]++;
}
unordered_set vis;
vis.insert(A);
unordered_map<string,int> cnt;
while(!que.empty()){
int n=que.size();
ans++;
int flag=1;
while(n–){
string st=que.front();
que.pop();
cnt[st]=ans;
if(st==B){
flag=0;
break;
}
for(int i=0;i<st.size();i++){
for(int j=0;j<26;j++){
char t=st[i];
if(t==(j+‘a’)){
continue;
}
st[i]=(j+‘a’);
if(mp.find(st)!=mp.end() && vis.find(st)==vis.end()){
vis.insert(st);
que.push(st);
}
st[i]=t;
}
}
}
if(flag==0){
break;
}
}
vector<vector > an;
vector t;
fun(cnt,B,A,an,t);
for(auto &a:an){
reverse(a.begin(),a.end());
}
return an;
}