from string import ascii_lowercase
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: Set[str]
:rtype: int
"""
if beginWord == endWord:
return 1
wordList.remove(beginWord)
wordList.remove(endWord)
frontier = set([beginWord])
otherside = set([endWord])
visited = set()
pathLength = 1
while len(frontier) > 0 and len(otherside) > 0:
pathLength += 1
nexts = set()
for cur in frontier:
for perm in self.permutations(cur):
if perm in otherside:
return pathLength
if perm not in visited and perm in wordList:
visited.add(perm)
nexts.add(perm)
frontier = nexts
if len(frontier) > len(otherside):
frontier, otherside = otherside, frontier
return 0
def permutations(self, word):
for i in range(len(word)):
for c in ascii_lowercase:
yield word[:i] + c + word[i+1:]