The problem is described at Word Ladder II .

Algorithm 1

public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> res = new ArrayList<>();
List<String> list = new LinkedList<>();
Map<String, List<String>> children = new HashMap<>();

if (! wordList.contains(endWord)) {
return Collections.emptyList();
}

Queue<String> q = new LinkedList<>();
Set<String> visited = new HashSet<>();
Set<String> unvisited = new HashSet<>(wordList);
q.offer(beginWord);
unvisited.remove(beginWord);

boolean found = false;

while (! q.isEmpty()) {
int size = q.size();

for (int k = size - 1; k >= 0; k --) {
String word = q.poll();
for (int i = 0; i < word.length(); i++) {
char[] chs = word.toCharArray();
char c0 = chs[i];
for (char c = 'a'; c <= 'z'; c ++) {
chs[i] = c;
String newStr = new String(chs);

if (unvisited.contains(newStr)) {//only valid when the new str is dict
if (! visited.contains(newStr)) {
visited.add(newStr);
q.offer(newStr);
}

// here we construct an adjcement graph in the BFS process, each
// pointing from achived word to original word
if (children.containsKey(newStr)) {
children.get(newStr).add(word);
} else {
List<String> l = new ArrayList<>();
l.add(word);
children.put(newStr, l);
}

if (newStr.equals(endWord)) {
found = true;
}
}



} // a-z

chs[i] = c0;
}// fist index ---- last index
} // for each string

if (found) {
break;
}
unvisited.removeAll(visited); // clear the stack
visited.clear();
}

backTrace(endWord, beginWord, children, list, res); // back

return res;
}


private void backTrace(String cur, String start, Map<String, List<String>> children, List<String> list, List<List<String>> res) {
if (Objects.equals(cur, start)) {
list.add(0, cur);
res.add(new ArrayList<>(list));
list.remove(0);
return;
}

list.add(0, cur);

if (children.get(cur) != null) {
for (String str : children.get(cur)) {
backTrace(str, start, children, list, res);
}
}

list.remove(0);

}

// use dfs, that comes from beginWord to endWord
public void dfs(String word, String endWord, Map<String, List<String>> from, List<String> curr, List<List<String>> ans) {
if (Objects.equals(word, endWord)) {
ArrayList<String> oneAns = (ArrayList) ((ArrayList)curr).clone();
ans.add(oneAns);
return;
}

if (! from.containsKey(word)) {
return;
}

for (String w :
from.get(word)) {
curr.add(w);
dfs(w, endWord, from, curr, ans);
curr.remove(w);
}

}

Algorithm 2

public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> rst = new ArrayList<>();

HashSet<String> dict = new HashSet<>(wordList);

if (!dict.contains(endWord)) {
return Collections.emptyList();
}

Map<String, List<String>> childrenMap = new HashMap<>();
Map<String, Integer> distanceMap = new HashMap<>();

Queue<String> q = new LinkedList<>();
dict.add(beginWord);
q.offer(beginWord);
distanceMap.put(beginWord, 0);

for (String s : dict) {
childrenMap.put(s, new ArrayList<>());
}

while (!q.isEmpty()) {
String str = q.poll();
List<String> list = transform(dict, str);
Objects.requireNonNull(list).forEach(s -> {
childrenMap.get(str).add(s);
if (! distanceMap.containsKey(s)) {
distanceMap.put(s, distanceMap.get(str) + 1);
q.offer(s);
}
});
}

bfs(beginWord, endWord, childrenMap, distanceMap, rst);

return rst;
}

private List<String> transform(Set<String> dict, String word) {
List<String> candidates = new ArrayList<>();
StringBuilder sb = new StringBuilder(word);
for (int i = 0; i < sb.length(); i++) {
char tmp = sb.charAt(i);
for (char c = 'a'; c <= 'z'; c++) {
if (tmp == c) continue;
sb.setCharAt(i, c);
String newWord = sb.toString();
if (dict.contains(newWord)) {
candidates.add(newWord);
}
}
sb.setCharAt(i, tmp);
}
return candidates;
}

public void bfs(String start, String end, Map<String, List<String>> childrenMap, Map<String, Integer> distanceMap, List<List<String>> rst) {
Queue<List<String>> q = new LinkedList<>();
List<String> list = new ArrayList<>();
list.add(end);
q.offer(new ArrayList<>(list));

while (!q.isEmpty()) {
int size = q.size();
while (size > 0) {
list = q.poll();
String str = list.get(0);

for (String s : childrenMap.get(str)) {
list.add(0, s);

if (s.equals(start)) {
rst.add(new ArrayList<>(list));
} else if (distanceMap.containsKey(s) && distanceMap.get(str) - 1 == distanceMap.get(s)) { // check str and s is an adjcement
q.offer(new ArrayList<>(list));
}

list.remove(0);
}

size --;
}
}
}