# 126. Word Ladder II¶

## Information¶

Diffculty: Hard

Created: 2020-03-11 09:04:00

Last Motified: 2020-03-11 09:33:13

Tags: Array, String, Backtracking, Breadth-first Search

## Intuition¶

If two words is only has one letter different, then we could change from one to another. And we could treat this relationship as a link. So all the word from the list contruct a graph. So this problem could be solved by 2 steps.

Construct the graph, get the adjancent list.

Do a BFS to get the distance from the start node to each node.

Back track to get all possible path.

For the second part, the time complexity is O(n + l) where n is the number of words and l is the number of connections.

For the first part, there could be multiple ways to contruct the graph. One way is for every pair of words, check if they are linked. The time complexity of this way is O(n ^ 2 * m), where m is the length of the words. And another way it to setup a dictionary to save all words and their indexes. Then, for each word, check all possible connected words if they are in the dictionary. The time complexity of this way is O(n * m * 26 * m) = O(n * m ^ 2).

I assume that the word length is smaller than the number of words in the list, so I use the second way to construct the graph.

## Solution¶

```
import string
from collections import deque
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
if endWord not in wordList:
return []
wordList.append(beginWord)
n = len(wordList)
wordIndexes = {}
for i, w in enumerate(wordList):
wordIndexes[w] = i
# Construct the graph
adj = [set() for _ in range(n)]
for i, w in enumerate(wordList):
for j in range(len(w)):
for c in string.ascii_lowercase:
if w[j] == c:
# No self loop
continue
tmp = w[:j] + c + w[j + 1:]
if tmp in wordIndexes:
k = wordIndexes[tmp]
adj[i].add(k)
adj[k].add(i)
# The first element of each node in parent is the minimum length to
# reach it.
distance = [float('inf')] * n
distance[n - 1] = 0
queue = deque([n - 1])
while queue:
current = queue.popleft()
for child in adj[current]:
if distance[child] <= distance[current] + 1:
continue
distance[child] = distance[current] + 1
queue.append(child)
# Back tracking to get all the paths
target = wordIndexes[endWord]
ans = []
path = []
self._dfs(n - 1, 0, adj, distance, path, ans, target)
# Convert indexes to words
for row in ans:
for i in range(len(row)):
row[i] = wordList[row[i]]
return ans
def _dfs(self, node, depth, adj, distance, path, ans, target):
if distance[node] != depth:
return
path.append(node)
if target == node:
ans.append(path[:])
else:
for child in adj[node]:
self._dfs(child, depth + 1, adj, distance, path, ans, target)
path.pop()
return
```