# 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):
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) {
}
short_path();
if (dist.get(endWord) == null) return res;
List<String> path = new ArrayList();
dfs(endWord, path);
return res;
}

private void short_path() {
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);
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)) {
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;
}
};