# Python easy BFS

• ``````import collections
class Solution(object):
def minMutation(self, start, end, bank):
"""
:type start: str
:type end: str
:type bank: List[str]
:rtype: int
"""
visited = set()
bank_set = set(bank)
queue = collections.deque()
queue.append(start)
cnt = -1
while queue:
cnt += 1
size = len(queue)
for _ in range(size):
current = queue.popleft()
if current == end:
return cnt
for gene in self.possible_mutation(current, bank):
if gene not in visited:
queue.append(gene)

return -1

def possible_mutation(self, current, bank):
poss_mut = []
for gene in bank:
diff = 0
for i in range(8):
if current[i] != gene[i]:
diff += 1
if diff > 1:
break
if diff == 1:
poss_mut.append(gene)

return poss_mut

``````

• @Jason1016 Similar to yours, but instead of adding to an visited set, I remove from a not_visited set and use this not_visited set in the possible_mutation function.

``````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
"""
not_visited = set(bank)

def mutations_generator(gene):
for mutation in list(not_visited):
diff = 0
for i in range(0, len(gene)):
if diff > 1:
continue
elif gene[i] != mutation[i]:
diff += 1
if diff == 1:
not_visited.remove(mutation)
yield mutation

open_nodes = deque()

open_nodes.append((start, 0))

while len(open_nodes) > 0:
gene_tuple = open_nodes.pop()

if gene_tuple[0] == end:
return gene_tuple[1]

next_mutation_count = gene_tuple[1] + 1

for mutation in mutations_generator(gene_tuple[0]):
open_nodes.append((mutation, next_mutation_count))

return -1
``````

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