class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
"""
#wordList.append(endWord)
q = []
q.append((beginWord,1))
while q:
(curr,lenth) = q.pop(0)
if curr == endWord:
return lenth
for i in range(len(curr)):
part1 = curr[:i]
part2 = curr[i+1:]
for j in 'abcdefghijklmnopqrstuvwxyz':
if curr[i] != j:
nextword = part1 + j + part2
if nextword in wordList:
q.append((nextword,lenth+1))
wordList.remove(nextword)
return 0
但这一题其实是在卡时间，卡的比较严格，所以需要把wordlist换成python字典格式，这样在搜索的时候就从o(n)变成o(1)了
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: Set[str]
:rtype: int
"""
dic = {}
for w in wordList:
if w not in dic:
dic[w] = 1
q = [(beginWord,1)]
while q:
e,lens = q.pop(0)
if e == endWord: return lens
for i in range(len(e)):
left = e[:i]
right = e[i + 1:]
for c in 'abcdefghigklmnopqrstuvwxyz':
if e[i] != c:
nextWord = left + c + right
if nextWord in dic:
q.append((nextWord,lens + 1))
del dic[nextWord]
return 0
