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
Python Solution using BFS



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.



@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) ~