Leetcode Word Ladder II problem solution

In this Leetcode Word Ladder II problem solution we have Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s1, s2, ..., sk].

Problem solution in Python.

class Solution(object):
    def findLadders(self, beginWord, endWord, wordList):
        abc='abcdefghijklmnopqrstuvwxyz'
        wordList=[beginWord]+wordList
        start=0
        try:
            end=wordList.index(endWord)
        except:
            return []
        n=len(wordList)
        l=len(beginWord)
        conn=[[] for i in range(n)]
        d=dict()
        for i in range(n):
            d[wordList[i]]=i
        for i in range(n):
            for j in range(l):
                for k in range(len(abc)):
                    s=wordList[i][:j]+abc[k]+wordList[i][j+1:]
                    if d.get(s,-1)>=0:
                        conn[i].append(d[s])
        valid=[0]*n
        valid[start]=1
        step=1
        wordbag=[[start],[]]
        path=[[] for i in range(n)]
        path[start]=[[beginWord]]
        while len(wordbag[1-step%2])>0:
            step+=1
            wordbag[1-step%2]=[]
            for i in wordbag[step%2]:
                for j in conn[i]:
                    if valid[j]==0 or valid[j]==step:
                        if valid[j]==0:
                            wordbag[1-step%2].append(j)
                        valid[j]=step
                        for k in path[i]:
                            path[j].append(k+[wordList[j]])
            if valid[end]>0:
                break
        return path[end]

Problem solution in Java.

class Solution {
    Set<String> set = new HashSet();
    String beginWord, endWord;
    Map<String, Integer> dist = new HashMap();
    List<List<String>> res;
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        this.beginWord = beginWord;
        this.endWord = endWord;
        this.res = new ArrayList();
        for (String word : wordList) {
            set.add(word);
        }
        short_path();
        if (dist.get(endWord) == null) return res;
        List<String> path = new ArrayList();
        path.add(endWord);
        dfs(endWord, path);
        return res;
    }
    
    private void short_path() {
        Queue<String> q = new LinkedList();
        q.offer(beginWord);
        dist.put(beginWord, 0);
        while(q.size() > 0) {
            String cur = q.poll();
            if (cur.equals(endWord) ) break;
            char[] charCur = cur.toCharArray();
            for (int i = 0; i < cur.length(); i++) {
                char c = charCur[i];
                for (char j = 'a'; j <= 'z'; j++) {
                    charCur[i] = j;
                    String s = new String(charCur);
                    if (set.contains(s) && dist.get(s) == null) {
                        dist.put(s, dist.get(cur) + 1);
                        q.offer(s);
                    }
                    
                }
                charCur[i] = c;
            }
        }
    }
    
    private void dfs(String word, List<String> path) {
        if (word.equals(beginWord)) {
            List list = new ArrayList(path);
            Collections.reverse(list);
            res.add(list);
            return;
        }
        char[] charCur = word.toCharArray();
        for (int i = 0; i < word.length(); i++) {
            char c = charCur[i];
            for (char j = 'a'; j <= 'z'; j++) {
                charCur[i] = j;
                String s = new String(charCur);
                if (dist.get(s) != null && dist.get(s) + 1 == dist.get(word)) {
                    path.add(s);
                    dfs(s, path);
                    path.remove(path.size() - 1);
                }
                    
            }
            charCur[i] = c;
        }
    }
}

Problem solution in C++.

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_map<string,int> um;
        vector<vector<string>> res;
        for(const auto w:wordList) um.insert({w,INT_MAX});
        um[beginWord]=0;  
        queue<pair<string,vector<string>>> q;
		
        q.push({beginWord,{beginWord}});
		
        while(!q.empty()){
            auto n=q.front();
            q.pop();

            string w=n.first;
            auto v=n.second;
            if(w==endWord){
                res.push_back(v);
                continue;
            } 
			
            for(int i=0;i<w.size();i++){
                string t=w;
                for(char c='a';c<='z';c++){
                    t[i]=c;
                    if(t==w) continue;
                    if(um.find(t)==um.end()) continue;  
                    if(um[t]<(int)v.size()) continue; 
                    um[t]=(int)v.size();
                    v.push_back(t);
                    q.push({t,v});
                    v.pop_back();
                }
            }
        }
        return res;
    }
};