原題
給出兩個(gè)單詞（start和end）和一個(gè)字典掂咒，找出所有從start到end的最短轉(zhuǎn)換序列
比如：
1.每次只能改變一個(gè)字母。
2.變換過程中的中間單詞必須在字典中出現(xiàn)。
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
返回
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
注意
- 所有單詞具有相同的長度败去。
- 所有單詞都只包含小寫字母。
解題思路
- 首先烈拒，善用一個(gè)條件圆裕，所有的單詞長度相同
- 建立一個(gè)index广鳍，作用就是把去掉某一個(gè)位置的字母后，剩余部分相同的放入一個(gè)桶中吓妆。為了優(yōu)化時(shí)間復(fù)雜度赊时。比如
"abcd" -> (1, bcd) <- "fbcd"
- BFS一遍，確定為一個(gè)單詞在圖中的第幾層
- DFS一遍行拢，找到每一個(gè)可行的路線祖秒。此時(shí)BFS的作用就是從第n層只能往n+1層走，以保證最短路徑
- 為什么使用
dict.get(key)而不是dict[key]舟奠？
# 可以設(shè)定一個(gè)default value, 如果key不存在竭缝，就建立相應(yīng)的key-value pair
a = dictionary.get("bogus", None) # return None
a = dictionary["bogus"] # raise KeyError
完整代碼
import Queue
class Solution(object):
def buildIndex(self, length, dict):
indexes = []
for i in range(length):
index = {}
for word in dict:
entry = word[:i] + word[i + 1:]
words = index.get(entry, [])
words.append(word)
index[entry] = words
indexes.append(index)
return indexes
def getNextWord(self, word):
res = []
for i in range(len(word)):
entry = word[:i] + word[i + 1:]
if entry in self.indexes[i]:
for nextWord in self.indexes[i][entry]:
if nextWord != word:
res.append(nextWord)
return res
def BFS(self, start, end):
self.distance = {}
self.distance[start] = 0
q = Queue.Queue()
q.put(start)
while not q.empty():
head = q.get()
for nextWord in self.getNextWord(head):
if nextWord not in self.distance:
self.distance[nextWord] = self.distance[head] + 1
q.put(nextWord)
def DFS(self, current, target, path):
if current == target:
self.result.append(path[:])
return
for word in self.getNextWord(current):
if self.distance[word] - 1 == self.distance[current]:
self.DFS(word, target, path + [word])
def findLadders(self, beginWord, endWord, wordlist):
"""
:type beginWord: str
:type endWord: str
:type wordlist: Set[str]
:rtype: List[List[int]]
"""
if beginWord is None or endWord is None or len(beginWord) != len(endWord):
return []
if beginWord not in wordlist or endWord not in wordlist:
return []
self.indexes = self.buildIndex(len(beginWord), wordlist)
self.BFS(beginWord, endWord)
self.result = []
if beginWord in self.distance:
self.DFS(beginWord, endWord, [beginWord])
return self.result
