Description
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.
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.
Solutions
1. Backtracking
注意要找最短路径，我是从遍历所有结果后再找最小的，没有做好剪枝，导致了 TLE。
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
res = []
self.alpha = string.ascii_lowercase # a-z
self.max = float('inf')
visited = set()
visited.add(beginWord)
self.dfs(endWord, set(wordList), visited, beginWord, [beginWord], res)
min_len = self.find_min_len(res)
return [path for path in res if len(path) == min_len]
def find_min_len(self, res):
min_len = float('inf')
for path in res:
size = len(path)
if size < min_len:
min_len = size
return min_len
def dfs(self, endWord, wordList, visited, word, path, res):
if word == endWord:
size = len(path)
if size <= self.max:
self.max = size
res.append(path)
return
if len(path) > self.min:
return
n = len(word)
for i in range(n):
for ch in self.alpha:
new_word = word[:i] + ch + word[i+1:]
if new_word in wordList and new_word not in visited:
visited.add(new_word)
self.dfs(endWord, wordList, visited, new_word, path+[new_word], res)
visited.remove(new_word)
# TLE
回溯参考：
# Time: O()
# Space: O()
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
tree, words, n = collections.defaultdict(set), set(wordList), len(beginWord)
if endWord not in wordList: return []
found, q, nq = False, {beginWord}, set()
while q and not found:
words -= set(q)
for x in q:
for y in [x[:i]+c+x[i+1:] for i in range(n) for c in 'qwertyuiopasdfghjklzxcvbnm']:
if y in words:
if y == endWord:
found = True
else:
nq.add(y)
tree[x].add(y)
q, nq = nq, set()
def bt(x):
return [[x]] if x == endWord else [[x] + rest for y in tree[x] for rest in bt(y)]
return bt(beginWord)
# Runtime: 532 ms, faster than 35.67%
# Memory Usage: 16.7 MB, less than 16.67%
2. BFS
还是用 BFS 试一下。
# Time: O()
# Space: O()
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
all_adj_combine = collections.defaultdict(list)
wordLen = len(beginWord)
for w in wordList:
for i in range(wordLen):
all_adj_combine[w[:i] + "*" + w[i + 1:]].append(w)
level = {}
for w in wordList:
level[w] = float("inf")
level[beginWord] = 0
# BFS
res = []
size = float("inf")
queue = [(beginWord, [beginWord])]
while queue:
word, path_list = queue.pop(0)
if len(path_list) >= size:
return res
for i in range(wordLen):
adj_words = all_adj_combine[word[:i] + "*" + word[i + 1:]]
for adj_w in adj_words:
if adj_w == endWord:
res.append(path_list + [adj_w])
size = len(path_list + [adj_w])
elif level[adj_w] > level[word]:
queue.append((adj_w, path_list + [adj_w]))
level[adj_w] = level[word] + 1
return res
# Runtime: 348 ms, faster than 71.55%
# Memory Usage: 17.7 MB, less than 8.33%