Word Ladder II
Created: November 30, 2019 by [lek-tin]
Last updated: November 30, 2019
Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
- Only one letter can be changed at a time
- Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
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.
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.
Solution
end -> start: bfs start -> end: dfs
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 []
lookup = set(wordList)
lookup.add(beginWord)
lookup.add(endWord)
distance = {}
# record distances
# from endWord to startWord
self.bfs(endWord, distance, lookup)
# beginWord: "hit"
# endWord: "cog"
# wordList: ["hot","dot","dog","lot","log","cog"]
# distance: {'cog': 0, 'dog': 1, 'log': 1, 'dot': 2, 'lot': 2, 'hot': 3, 'hit': 4}
results = []
# backtracking
self.dfs(beginWord, endWord, distance, lookup, [beginWord], results)
return results
def bfs(self, start, distance, lookup):
distance[start] = 0
queue = deque([start])
while queue:
word = queue.popleft()
for next_word in self.get_next_words(word, lookup):
if next_word not in distance:
distance[next_word] = distance[word] + 1
queue.append(next_word)
def get_next_words(self, word, lookup):
words = []
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
next_word = word[:i] + c + word[i + 1:]
if next_word != word and next_word in lookup:
words.append(next_word)
return words
def dfs(self, curr, target, distance, lookup, path, results):
if curr == target:
results.append(list(path))
return
for word in self.get_next_words(curr, lookup):
if distance[word] != distance[curr] - 1:
continue
path.append(word)
self.dfs(word, target, distance, lookup, path, results)
path.pop()