## 126. Word Ladder II

Given two words (beginWord_and_endWord), and a dictionary's word list, find all shortest transformation sequence(s) frombeginWord_to_endWord, such that:

1. Only one letter can be changed at a time
2. Each transformed word must exist in the word list. Note that _beginWord _is _not _a transformed word.

Note:

• Return an empty list if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume _beginWord _and _endWord _are non-empty and are not the same.

Example 1:

``````Input:

beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output:
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
``````

Example 2:

``````Input:

beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: []

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
``````

Thoughts:

1. "Naive" Solution: Create a dictionary that maps <str word, List[List[str]]]> Solution lists. Initialize the layer[beginword] word as [[beginword]].

1. Expanding the layer list as follows:
1. Having a childLayer which maps the layer for the next step
2. while current layer is not empty
1. for each w in layers keys:
2. if w is in the EndWord: res list record the results by taking all the elements of layer[w]
3. else for every position, flop the word w as neww. check if neww is in the wordList: add neww after every path in layer[w], add this result into childLayer[neww]
4. set layer to newLayer for the next iteration
5. remvoe all the keys from wordList that is in newlayers
2. BFS + DFS:

1. Shortest transformation: BFS to find the shortest path between start and end

2. Find all the transformation: DFS with backtracking to find all the answer

Code: T:O(L^3*l) ? (L as wordList length, l as word length). S:O(L^3*l)?

``````class Solution(object):
def findLadders(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: List[List[str]]
"""
wordList = set(wordList)
res,layer = [], {}
layer[beginWord] = [[beginWord]]

while layer:
newlayer = collections.defaultdict(list)
for w in layer:
if w == endWord:
res += [k for k in layer[w]]
else:
for i in range(len(w)):
for c in string.ascii_lowercase:
neww = w[:i] + c + w[i+1:]
if neww in wordList:
newlayer[neww]+= [j + [neww] for j in layer[w]]
wordList -= set(newlayer.keys()) # for avoiding unsupported operation between sets and list

layer = newlayer

return res
``````

Code: BFS + DFS

``````class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
HashSet<String> dict = new HashSet<>(wordList);
List<List<String>> res = new ArrayList<>();
Map<String, Integer> distance = new HashMap<>();
Map<String, ArrayList<String>> neighbors = new HashMap<>();
ArrayList<String> solution = new ArrayList<>();
bfs(beginWord, endWord, dict, distance, neighbors);
dfs(beginWord, endWord, dict, distance, neighbors, solution, res);
return res;
}

private void bfs(String start, String end, Set<String> dict,  Map<String, Integer> distance, Map<String, ArrayList<String>> nodeNeighbors) {
for (String str : dict)
nodeNeighbors.put(str, new ArrayList<String>());
Queue<String> queue = new LinkedList<String>();
queue.offer(start);
distance.put(start, 0);

while (!queue.isEmpty()) {
int count = queue.size();
boolean foundEnd = false;
for (int i = 0; i < count; i++) {
String cur = queue.poll();
int curDistance = distance.get(cur);
List<String> neighbors = getNeighbors(cur, dict);

for (String neighbor : neighbors) {
// System.out.println(cur);
if (!distance.containsKey(neighbor)) {// Check if visited
distance.put(neighbor, curDistance + 1);
if (end.equals(neighbor))// Found the shortest path
foundEnd = true;
else
queue.offer(neighbor);
}
}
}

if (foundEnd)
break;
}
}

private void dfs(String cur, String end, Set<String>dict , Map<String, Integer> distance, Map<String, ArrayList<String>> neighbors, List<String> solution, List<List<String>> res){
// found end: add
if(end.equals(cur)) res.add(new ArrayList<String> (solution));
// not found yet: recursively calling dfs
else{
for(String next: neighbors.get(cur)){
if(distance.get(next) == distance.get(cur) + 1)
dfs(next, end, dict, distance, neighbors, solution, res);
}
}
solution.remove(solution.size() - 1);
}

private List<String> getNeighbors(String node, Set<String> dict){
List<String> res = new ArrayList<>();
char chs []  = node.toCharArray();
for(char ch = 'a'; ch <= 'z'; ch++){
for(int i = 0 ; i < chs.length; i++){
char old = chs[i];
chs[i] = ch;
if(dict.contains(String.valueOf(chs))){
}
chs[i] = old;
}
}

return res;
}

}
``````