原題
給出兩個單詞（start和end）和一個字典，找到從start到end的最短轉(zhuǎn)換序列
比如：
1.每次只能改變一個字母晚吞。
2.變換過程中的中間單詞必須在字典中出現(xiàn)杨凑。
start = "hit"
end = "cog"
dict = ** ["hot","dot","dog","lot","log"]**
一個最短的變換序列是
"hit"->"hot" -> "dot"->** "dog"->"cog"** 返回它的長度 5
注意:
- 如果沒有轉(zhuǎn)換序列則返回0。
- 所有單詞具有相同的長度漫雷。
- 所有單詞都只包含小寫字母颂龙。
解題思路
- 無向圖求最短路 - BFS 中的level order
# 即每次count一下這一層的size()习蓬，然后遍歷這一層
size = q.qsize()
for i in range(size):
- 題目中如果提到單詞，要考慮到單詞長度一般是有限的措嵌，進(jìn)行優(yōu)化
- 如何找通過一次改變可以形成的單詞在不在字典中躲叼，假設(shè)單詞長度為L，變量單詞企巢，每個位置可以有26種變換枫慷，所以O(shè)(L*26)，再check是否存在在字典中O(1)復(fù)雜度（更精確，應(yīng)該是O(L)的復(fù)雜度）
- ord('a') => 97 / chr(97) => a
- Java中的
HashSet<xxx>可以用Python中的Set() - 注意Python中string是immutable
import string
aToz = string.ascii_lowercase
# 'str' object does not support item assignment
newWord[i] = 'a'
# 所以或听，換種方式
newWord = current[:i] + 'a' + current[i+1:]
完整代碼
import Queue
import string
class Solution(object):
def getNextWord(self, word, dict):
aToz = string.ascii_lowercase
res = []
for char in aToz:
for j in range(len(word)):
if word[j] == char:
continue
newWord = word[:j] + char + word[j+1:]
if newWord in dict:
res.append(newWord)
return res
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: Set[str]
:rtype: int
"""
if not wordList:
return 0
q = Queue.Queue()
visited = set()
q.put(beginWord)
visited.add(beginWord)
length = 1
while not q.empty():
length += 1
size = q.qsize()
for i in range(size):
word = q.get()
for nextWord in self.getNextWord(word, wordList):
if nextWord in visited:
continue
if nextWord == endWord:
return length
q.put(nextWord)
visited.add(nextWord)
return 0
