定兩個單詞（beginWord 和 endWord）和一個字典械筛，找到從 beginWord 到 endWord 的最短轉(zhuǎn)換序列的長度拢切。轉(zhuǎn)換需遵循如下規(guī)則：
每次轉(zhuǎn)換只能改變一個字母。
轉(zhuǎn)換過程中的中間單詞必須是字典中的單詞。
說明:
如果不存在這樣的轉(zhuǎn)換序列，返回 0。
所有單詞具有相同的長度挥萌。
所有單詞只由小寫字母組成。
字典中不存在重復(fù)的單詞枉侧。
你可以假設(shè) beginWord 和 endWord 是非空的引瀑，且二者不相同。
示例 1:
輸入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
輸出: 5
解釋: 一個最短轉(zhuǎn)換序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
返回它的長度 5榨馁。
示例 2:
輸入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
輸出: 0
解釋: endWord "cog" 不在字典中憨栽，所以無法進(jìn)行轉(zhuǎn)換。
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
if endWord not in wordList:
return 0
wordList = set(wordList)
forward, backward, n, cnt = {beginWord}, {endWord}, len(beginWord), 2
dic = set(string.ascii_lowercase)
while len(forward) > 0 and len(backward) > 0:
if len(forward) > len(backward): # 加速
forward, backward = backward, forward
next = set()
for word in forward:
for i, char in enumerate(word):
first, second = word[:i], word[i + 1:]
for c in dic: # 遍歷26個字母
candidate = first + c + second
if candidate in backward: # 如果找到了，返回結(jié)果屑柔，沒有找到屡萤，則在wordList中繼續(xù)尋找
return cnt
if candidate in wordList:
wordList.discard(candidate) # 從wordList中去掉單詞
next.add(candidate) #加入下一輪的bfs中
forward = next
cnt += 1
return 0
