題目出處
難度
hard
個人範例程式碼
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
if endWord not in wordList:
return []
wordList.append(beginWord)
distance = {}
self.bfs(endWord, distance, wordList) # from end to start
self.ans = []
self.dfs(beginWord, endWord, distance, wordList, [beginWord]) # from start to end
return self.ans
def bfs(self, start, distance, worddict):
distance[start] = 0
queue = deque([start])
while queue:
word = queue.popleft()
print(self.get_next_words(word, worddict))
for next_word in self.get_next_words(word, worddict):
if next_word not in distance:
distance[next_word] = distance[word] + 1
queue.append(next_word)
def get_next_words(self, word, worddict):
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 worddict:
words.append(next_word)
# print(words)
return words
def dfs(self, cur, target, distance, worddict, path):
# print(distance)
if cur == target:
self.ans.append(path[:])
return
for word in self.get_next_words(cur, worddict): # different way will see other things
if word not in distance: # single node
continue
if distance[word] != distance[cur] - 1:
continue
path.append(word)
self.dfs(word, target, distance, worddict, path)
path.pop() # backtracking
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
算法說明
超難的一題，考了非常多概念，對細節處理的要求也非常多
我們先從建立圖片下手。
從 BFS 先找到最短路徑
題目的做成的文字圖有可能會有循環，我們需要先找最短路徑
透過最短路徑，反向 DFS 尋找所有結果
知道最短路徑後，我們才能用 DFS 將整個圖走過，
看在最短路徑的範圍當中，能夠找到有幾種結果。
- 先從 endWord 找回 start，再從 start 順便存路徑會最順。
注意處
從兩個起點搜尋的注意事項
這邊要處理在從兩端搜尋時，還是都要把每個點都看過一次，
例如上圖中下方的 graph 結構，我們會發現會有一些只靠單向搜尋「會距離很遠」的位置
獨立的點
有一種特殊的 case 是從起點開始，就根本就沒有任何的連線，
雖然這題的測資沒有考到，但這邊一樣有處理。
- 狀況大概如下圖：
只能說，這個就是細節處理的部分，萬一真的有這樣的情況，我們還是要回傳 []
input handling
如果 endWord 不在 worddict 中，return []
Boundary conditions
BFS 找最短路徑
搜尋至 queue 沒有東西的時候
「while queue」幫忙控制結束
DFS 找所有結果
反向搜尋至 distance 為 0 時結束，
我們在上一步驟中的 BFS，有順便記錄了 distance 最大的長度，
這邊就是反向操作到 0。
