# Fast and elegant two-end bfs solution in Python (~30 lines)

• ``````from collections import deque

class Solution(object):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
"""
def bfs():
# corner case
if end not in words:
return 0
# initialization
forth, back = deque(), deque()
dforth, dback = {}, {}
dforth[start] = 1
dback[end] = 1
forth.append(start)
back.append(end)
turn = True # if true it's forth turn, else back's
# loop in bfs order
while forth and back:
frontier = (forth if turn else back) or forth or back # frontier is not empty that way
distance = (dforth if turn else dback) or dforth or dback
word = frontier.popleft()
# found intersection
if ((frontier is forth and word in dback) or (frontier is back and word in dforth)):
return dforth[word] + dback[word] - 1 # word was counted twice
# for every position in the word, try all possible changes in character
for i in range(word_length):
for ch in 'abcdefghijklmnopqrstuvxwyz':
new_word = word[:i] + ch + word[i + 1:]
# new_word not visited and in the word dictionary
if new_word in words and new_word not in distance:
distance[new_word] = distance[word] + 1
frontier.append(new_word)
turn = not turn
return 0
word_length = len(start)
words = set(word_list)
return bfs()
``````

• It's a neat way to track depth of each node, but it doubles space complexity.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.