Untitled

mail@pastecode.io avatar
unknown
plain_text
23 days ago
1.8 kB
1
Indexable
Never
bool transformationPossible(string a, string b){
        int count = 0;
        for(int i =0; i<a.size(); i++){
            if(a[i]!=b[i]) count++;
        }
        if(count==1) return true;
        else return false;
    }

    vector<vector<string>> findSequences(string startWord, string targetWord, vector<string>& wordList) {
        int V = wordList.size();
        int targetIndex = -1, startIndex=-1;
        for(int i =0; i<V; i++){
            if(wordList[i]==startWord)startIndex=i;
            if(wordList[i]==targetWord)targetIndex=i;
        }
        if(startIndex==-1){
            wordList.push_back(startWord);
            startIndex=V;
            V++;
        }
        vector<int> adj[V];
        for(int i =0; i<V; i++){
            for(int j = i+1; j<V; j++){
                if(transformationPossible(wordList[i], wordList[j])){
                    adj[i].push_back(j);
                    adj[j].push_back(i);
                };
            }
        }
        vector<int>dist(V, INT_MAX);
        vector<vector<string>>paths;
        queue<vector<int>>q;
        q.push({startIndex});
        while(!q.empty()){
            vector<int>path = q.front(); // We only want the last added element
            int u = path.back();
            q.pop();
            if(u==targetIndex) {
                vector<string>res;
                for(int i =0; i<path.size(); i++){
                    res.push_back(wordList[path[i]]);
                }
                paths.push_back(res);
            }
            for(int v: adj[u]){
                if(dist[v]>=dist[u]+1){
                    path.push_back(v);
                    q.push(path);
                    path.pop_back();
                    dist[v]=dist[u]+1;
                }
            }
        }
        return paths;
    }
Leave a Comment