Python Solution using BFS


  • 3
    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
    

  • 0
    S

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


  • 0

    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.


  • 0
    S

    @lee12jin Thanks for your answer. :)


  • 0

    @sunnyS No prob :)


  • 0
    S

    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!


  • 0

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


  • 0
    S

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


Log in to reply
 

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