Solutions to LeetCode 126 Word Ladder II.
LeetCode 126
Word Ladder II (Hard) [link] (Incompleted)
class Solution:
def findLadders(self, beginWord, endWord, wordList):
wordList.append(beginWord)
wordList.append(endWord)
word2neighbors = self.get_neighbors(wordList)
word2dist = self.bfs(word2neighbors, beginWord, endWord)
results = []
self.dfs(word2dist, word2neighbors, endWord, beginWord, [endWord], results)
return results
def get_neighbors(self, dict):
word2neighbors = collections.defaultdict(list)
for word in dict:
for i in range(len(word)):
for char in 'abcdefghijklmnopqrstuvwxyz':
if char == word[i]:
continue
transword = word[:i] + char + word[i+1:]
if transword not in dict:
continue
word2neighbors[word].append(transword)
return word2neighbors
def bfs(self, word2neighbors, start, end):
word2dist = {start : 1}
queue = collections.deque([start])
while queue:
word = queue.popleft()
for neighbor in word2neighbors[word]:
if neighbor in word2dist:
continue
word2dist[neighbor] = word2dist[word] + 1
queue.append(neighbor)
return word2dist
def dfs(self, word2dist, word2neighbors, curr, start, result, results):
if curr == start:
results.append(list(result)[::-1])
return
for neighbor in word2neighbors[curr]:
if neighbor not in word2dist or word2dist[neighbor] != word2dist[curr] - 1:
continue
result.append(neighbor)
self.dfs(word2dist, word2neighbors, neighbor, start, result, results)
result.pop()
