Word ladder II
August 14, 2022
graphProblem URL: Word ladder II
We will first run a BFS to create the graph with adjacency list. Then we will run DFS to find all possible paths of that graph.
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
wordList = set(wordList)
if endWord not in wordList:
return []
# BFS visit
curr_level = {beginWord}
parents = collections.defaultdict(list)
while curr_level:
wordList -= curr_level
next_level = set()
for word in curr_level:
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + c + word[i+1:]
if new_word in wordList:
next_level.add(new_word)
parents[new_word].append(word)
if endWord in next_level:
break
curr_level = next_level
# DFS reconstruction
res = []
def dfs(word, path):
if word == beginWord:
path.append(word)
res.append(path[::-1])
else:
for p_word in parents[word]:
dfs(p_word, path + [word])
dfs(endWord, [])
return res
Time Complexity: O((n+m)*l)
, n is the number of words, m is number of edges(m = n^2), l is maximum word length
Space Complexity: O((n+m)*l)