Bfs solution by forming edges from relative words!


#1

vector<vector> adj;
vector<vector> parent;
vector<vector> paths;
vector path;
vector ans;

void find(int par)
{
if(par == 0)
{
reverse(path.begin(),path.end());
paths.push_back(path);
return;
}

for(auto u:parent[par])
{
   if(u!=-1)
   {
    path.push_back(ans[u]);
    
    find(u);
    
    path.pop_back();
   }
    
}

}

bool valid(string A, string B)
{
int count = 0;
if(A.size()==B.size())
{
for(int i=0;i<A.size();i++)
{
if(A[i]!=B[i])
{
count++;
}
}

    if(count==1)
    {
        return true;
    }
}

return false;

}

vector<vector > Solution::findLadders(string start, string end, vector &dict) {

paths.clear();
path.clear();
ans.clear();

/*
ans.push_back(start);
cout<<start;
for(auto c: dict)
{
ans.push_backĀ©;
cout<<c;
}

cout<<end;
ans.push_back(end);
*/

ans = dict;

int n = ans.size();

if(ans[0]==ans[n-1])
{
    return {{ans[0]}};
}
//cout<<n;
adj.assign(n,{});
parent.assign(n,{});
vector<int> visited(n,0);
vector<int> dist(n,2e9);




for(int i=0;i<ans.size();i++)
{
    for(int j=i+1;j<ans.size();j++)
    {
        
        if(valid(ans[i],ans[j]))
        {
            //cout<<i<<j;
            //paths.cl;out<<i<<j;
            adj[i].push_back(j);
            adj[j].push_back(i);
            
        }
    }
}

queue<int> q;

q.push(0);
dist[0] = 1;
parent[0] = {-1};

while(!q.empty())
{
    int u = q.front();
    q.pop();
    
    if(u==n-1)
    {
        break;
    }
    
    
    
    if(!visited[u])
    {
        visited[u] = true;
        for(auto v: adj[u])
        {
            if(dist[v]>1+dist[u])
            {
            dist[v] = 1+dist[u];
            q.push(v);
            parent[v].clear();
            parent[v].push_back(u);
            }
            
            else if(dist[v]==dist[u]+1)
            {
                parent[v].push_back(u);
            }
        }
        
    }
}

path.push_back(ans[n-1]);

find(n-1);




return paths;

}