-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path126_Word_Ladder_II.py
More file actions
94 lines (81 loc) · 3.21 KB
/
126_Word_Ladder_II.py
File metadata and controls
94 lines (81 loc) · 3.21 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
"""
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output:
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
"""
from collections import deque
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
wordList.append(beginWord)
wordList = set(wordList)
if endWord not in wordList:
return []
distance = {}
results = []
# KEY: Do BFS from "End to Start"
self.bfs(endWord, beginWord, distance, wordList)
# Do FDS from start to end
self.dfs(beginWord, endWord, distance, wordList, [beginWord], results)
return results
def bfs(self, beginWord, endWord, distance, wordList): # get distance from every word to target
queue = deque([beginWord])
distance[beginWord] = 0
while queue:
cur_word = queue.popleft()
# if cur_word == endWord: # KEY: 不可提前返回，會造成部分node沒有遍歷，導致key error
# return
for next_word in self.getNextWord(cur_word, wordList):
if next_word not in distance:
distance[next_word] = distance[cur_word] + 1
queue.append(next_word)
def getNextWord(self, word, wordList):
words = []
for i in range(len(word)):
for char in "abcdefghijklmnopqrstuvwxyz":
if char != word[i]:
next_word = word[:i] + char + word[i + 1:]
if next_word in wordList:
words.append(next_word)
return words
def dfs(self, beginWord, endWord, distance, wordList, path, results):
if beginWord == endWord:
results.append(list(path)) # dfs need deep copy
return
for next_word in self.getNextWord(beginWord, wordList):
if distance[next_word] == distance[beginWord] - 1: # KEY: choose the "shortest" path every time
# path.append(next_word)
self.dfs(next_word, endWord, distance, wordList, path + [next_word], results)
# path.pop()
import collections
class Solution:
def findLadders(self, beginWord, endWord, wordList):
wordList = set(wordList)
res = []
layer = {beginWord: [[beginWord]]}
while layer:
newlayer = collections.defaultdict(list)
for w in layer:
if w == endWord:
for r in layer[endWord]:
res.append(r)
else:
for next_word in self.getNextWord(w, wordList):
newlayer[next_word] += [j + [next_word] for j in layer[w]]
wordList -= set(newlayer.keys())
layer = newlayer
return res
def getNextWord(self, word, wordList):
words = []
for i in range(len(word)):
for char in "abcdefghijklmnopqrstuvwxyz":
if char != word[i]:
next_word = word[:i] + char + word[i + 1:]
if next_word in wordList:
words.append(next_word)
return words