# Short Python DFS/BFS beats 98%

• Very straight forward one. For DFS version, we can using `memo` to speed it up when test cases get bigger.

``````class Solution(object):
def minMutation(self, start, end, bank):
"""
:type start: str
:type end: str
:type bank: List[str]
:rtype: int
"""
def dfs(curr, step, seen):
if curr == end:
self.ans = min(self.ans, step)
else:
for NEXT in dic[curr] - seen:
dfs(NEXT, step+1 , seen | {NEXT})

dic = {a: {b for b in bank if sum(a[i] != b[i] for i in range(8)) == 1} for a in [start] + bank}
self.ans = float('inf')
dfs(start, 0, set())
return (self.ans, -1)[self.ans == float('inf')]
``````

And the BFS version as attached.

``````class Solution(object):
def minMutation(self, start, end, bank):
"""
:type start: str
:type end: str
:type bank: List[str]
:rtype: int
"""
dic = {a: {b for b in bank if sum(a[i] != b[i] for i in range(8)) == 1} for a in [start] + bank}
ans, queue, seen = float('inf'), collections.deque([(start, 0)]), set()
while queue:
curr, step = queue.popleft()
if curr == end: return step