# Python Solution using BFS

• ``````import collections

def viableMutation(current_mutation, next_mutation):
changes = 0
for i in xrange(len(current_mutation)):
if current_mutation[i] != next_mutation[i]:
changes += 1
return changes == 1

class Solution(object):
def minMutation(self, start, end, bank):
"""
:type start: str
:type end: str
:type bank: List[str]
:rtype: int
"""
queue = collections.deque()
queue.append([start, start, 0]) # current, previous, num_steps
while queue:
current, previous, num_steps = queue.popleft()
if current == end:  # in BFS, the first instance of current == end will yield the minimum
return num_steps
for string in bank:
if viableMutation(current, string) and string != previous:
queue.append([string, current, num_steps+1])
return -1
``````

• @lee12jin What's the time complexity of this one?

• BFS has a runtime of o(|V| + |E|) or o(|vertices| + |edges|) but we know that the number of edges is going to be overwhelmed by the o(|V|).
How? Everytime we visit a vertex, we have to go through every possible edge (string in bank), which is greater than or equal to the actual edges at every vertex. So, we need to calculate o(|V|) to get worst runtime.

I believe worst case time complexity is o(k * n * n * n)

where k = len of string, and n = number of strings in the bank.

Not confident in this answer, but I pictured how the outer while loop would scale with a growing n. Worst case, you have cycles in the graph and you have to go through every string in the bank to reach the end.

• @sunnyS No prob :)

• just a quick question, here what is major different if without using collection.deque() and use list.pop(0) instead? I did not see run time different. Thanks!

• @Seasean The runtimes for collection.deque().popleft() and list.pop(0) are different. The runtime for list.pop() is o(1) but as you pop closer to the front of the list (i.e. pop(0)) you have a runtime of o(n) AFAIK. Meanwhile, the implementation of collection.deque() is a doubly linked list, so popleft() and pop() are both o(1).

• @lee12jin Very thanks for your explanation. so can I say that the reason we use the deque here is only for popleft() that is O(1) ~

• Thanks for the solution!!!a small question. There might be possible of a infinite loop，you make the pre != next , but it can be the same after seven times. i think there might need a limit to the num_step.

• "AAAAAAAA"
"CCCAAAAA"
["CAAAAAAA","CCAAAAAA","ACAAAAAA","ACCAAAAA","AACAAAAA","CACAAAAA"]

axample like this show the problem

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