Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
Only one letter can be changed at a time Each intermediate word must exist in the dictionary
Example Given: start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"] As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList: return 0
wordDict = set(wordList)
visit = set()
q = []
count = 0
q.append(beginWord)
while q:
size = len(q)
count += 1
for i in range(size):
word = q.pop(0)
if word == endWord:
return count
for next_word in self.getNext(word, wordDict):
if next_word not in visit:
q.append(next_word)
# 假若next_word符合條件但是已經看過代表他會
# 形成更遠的分支，不予考慮
visit.add(next_word)
return 0
def getNext(self, word, wordDict):
next_list = []
for i in range(len(word)):
for j in range(26):
ch = chr(ord('a') + j)
if ch == word[i]: continue
new_word = word[:i] + ch + word[i+1:]
if new_word in wordDict:
next_list.append(new_word)
return next_list
126 Word Ladder II
Example Given: start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"] Return [ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ]
Hint: 1. Use BFS from end to start to record the distance of node to end
2. DFS to record all shortest path
Map the distance of node to end
Map surrounding Nodes
注意在bfs時先把
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
if endWord not in wordList: return []
self.wordDict = set(wordList)
# Add beginWord to wordDict, otherwise it will not be update when BFS
self.wordDict.add(beginWord)
self.neighbors = defaultdict(list)
self.distance = defaultdict(int)
self.ans = []
# use bfs to traverse from end to start, and record the nerghbors of each node and distance from end to each node
# distance will be update as the shortest distance to end
self.bfs(beginWord, endWord)
# dfs to find out the route
self.dfs([beginWord], endWord)
return self.ans
def dfs(self, l, endWord):
word = l[-1]
if word == endWord:
self.ans.append(l.copy())
for next_word in self.neighbors[word]:
l.append(next_word)
# only go to next level if on the correct route
if self.distance[word] == self.distance[next_word] + 1:
self.dfs(l, endWord)
l.pop()
def bfs(self, beginWord, endWord):
q = []
q.append(endWord)
flag = False
while q:
if flag: break
size = len(q)
for i in range(size):
word = q.pop(0)
for next_word in self.getNext(word):
if next_word == beginWord:
flag = True
self.neighbors[next_word].append(word)
# If we have seen the node distance means this one if farther distance. Not update
if next_word not in self.distance:
self.distance[next_word] = self.distance[word] + 1
q.append(next_word)
def getNext(self, word):
next_list = []
for i in range(len(word)):
for j in range(26):
ch = chr(ord('a') + j)
if word[i] == ch: continue
new_word = word[:i] + ch + word[i+1:]
if new_word in self.wordDict:
next_list.append(new_word)
return next_list
