class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: Set[str]
:rtype: int
"""
wordList.add(endWord)
cur=[beginWord] #possible transformation at each stage
l=len(beginWord)
distance=0 # keep track of the number of transformations
visited=set([beginWord]) #keep track of the set of visited words
while cur:
next=[] #temp list to store each possible transformation at each stage
for word in cur:
if word==endWord:
return distance+1
for i in xrange(l):
for j in 'abcdefghijklmnopqrstuvwxyz':
candidate=word[:i]+j+word[i+1:]
if candidate not in visited and candidate in wordList:
next.append(candidate)
visited.add(candidate)
distance+=1
cur=next
return 0
127. Word Ladder
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 原题 给出两个单词（start和end）和一个字典，找到从start到end的最短转换序列比如：1.每次只能改变一...
