Two end BFS in Python

• Slower than my expectation. Anyway, this is the best we can do.

``````from collections import deque
class Solution(object):
def minMutation(self, start, end, bank):
"""
:type start: str
:type end: str
:type bank: List[str]
:rtype: int
"""
def getNeighbors(word, dict):
ret = []
choices = ["A", "G", "C", "T"]

for i in xrange(0, len(word)):
for choice in choices:
newWord = word[:i] + choice + word[i + 1:]
if newWord in dict:
ret.append(newWord)
return ret
dict = {}
q1 = deque([(start, 0)])
q2 = deque([(end, 0)])
for b in bank:
if b in (start, end):
dict[b] = (b, 0)
else:
dict[b] = (None, None)
if end not in dict:
return -1

while q1 or q2:
if q1:
word, dist = q1.popleft()
for nbr in getNeighbors(word, dict):
source, curDist = dict[nbr]
if source == start:
continue
if source is None:
dict[nbr] = start, dist + 1
q1.append((nbr, dist + 1))
if source == end:
return curDist + dist + 1

if q2:
word, dist = q2.popleft()
for nbr in getNeighbors(word, dict):
source, curDist = dict[nbr]
if source == end:
continue
if source is None:
dict[nbr] = end, dist + 1
q2.append((nbr, dist + 1))
if source == start:
return curDist + dist + 1

return -1

``````

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