def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
"""
def construct_dict(wordList):
d = {}
for word in wordList:
for i in xrange(len(word)):
s = word[:i] + '_' + word[i + 1:]
d[s] = d.get(s, []) + [word]
return d
def bfs(begin, end, d):
queue, visited = collections.deque([(begin, 1)]), set()
while queue:
word, steps = queue.popleft()
if word not in visited:
visited.add(word)
if word == end:
return steps
for i in xrange(len(word)):
s = word[:i] + '_' + word[i + 1:]
neigh_words = d.get(s, [])
for neigh in neigh_words:
if neigh not in visited:
queue.append((neigh, steps + 1))
return 0
wordList = set(wordList)
d = construct_dict(wordList)
return bfs(beginWord, endWord, d)
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
"""
if endWord not in wordList:
return 0
length = 2
front, back = set([beginWord]), set([endWord])
wordList = set(wordList)
wordList.discard(beginWord)
while front:
front = wordList & (set(word[:i] + ch + word[i + 1:] for word in front for i in xrange(len(beginWord)) for ch in string.ascii_lowercase))
if front & back:
return length
length += 1
if len(front) > len(back):
front, back = back, front
wordList -= front
return 0