?LeetCode刷題實戰(zhàn)126：單詞接龍 II
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.
題意
給定兩個單詞（beginWord 和 endWord）和一個字典 wordList，找出所有從 beginWord 到 endWord 的最短轉(zhuǎn)換序列。轉(zhuǎn)換需遵循如下規(guī)則：
每次轉(zhuǎn)換只能改變一個字母。
轉(zhuǎn)換后得到的單詞必須是字典中的單詞。
說明:
如果不存在這樣的轉(zhuǎn)換序列，返回一個空列表。
所有單詞具有相同的長度。
所有單詞只由小寫字母組成。
字典中不存在重復的單詞。
你可以假設(shè) beginWord 和 endWord 是非空的，且二者不相同。
示例 1:
輸入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
輸出:
[
??["hit","hot","dot","dog","cog"],
? ["hit","hot","lot","log","cog"]
]
示例 2:
輸入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
輸出: []
解釋:?endWord "cog"?不在字典中，所以不存在符合要求的轉(zhuǎn)換序列。
解題
class?Solution:
????def?findLadders(self, beginWord:?str, endWord:?str, wordList:?List[str])?-> List[List[str]]:
????????wordList=set(wordList)
????????wordList.add(beginWord)
????????#wordList.append(beginWord)
????????dist=self.bfs(endWord,wordList)
????????res=[]
????????self.dfs(beginWord,endWord,wordList,dist,[beginWord],res)
????????return?res
????
????#bfs記錄點到終點的最短距離:end -> start
????def?bfs(self,begin,wordList):
????????dist={}
????????dist[begin]=0
????????queue=[begin]
????????while?queue:
????????????L=len(queue)
????????????for?_?in?range(L):
????????????????word=queue.pop(0)
????????????????for?w in?self.nextWord(word,wordList):
????????????????????if?w not?in?dist:
????????????????????????dist[w]=dist[word]+1
????????????????????????queue.append(w)
????????return?dist
????????
????#利用遞歸來記錄路徑：從start -> end
????def?dfs(self,curr,end,wordList,dist,path,res):
????????if?curr==end:
????????????res.append(list(path))
????????for?w in?self.nextWord(curr,wordList):
????????????if?dist[w]==dist[curr]-1:
????????????????path.append(w)
????????????????self.dfs(w,end,wordList,dist,path,res)
????????????????path.pop()
????????????????
????????
????def?nextWord(self,word,wordList):
????????res=[]
????????for?i in?range(len(word)):
????????????for?letter in?"abcdefghijklmnopqrstuvwxyz":
????????????????next_=word[0:i]+letter+word[i+1::]
????????????????if?next_!=word and?next_?in?wordList:
????????????????????res.append(next_)
????????return?res