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.
@lee12jin Thanks for your answer. :)
@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) ~
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.