Two end BFS in Python


  • 0

    Slower than my expectation. Anyway, this is the best we can do.

    from collections import deque
    class Solution(object):
        def minMutation(self, start, end, bank):
            """
            :type start: str
            :type end: str
            :type bank: List[str]
            :rtype: int
            """
            def getNeighbors(word, dict):
                ret = []
                choices = ["A", "G", "C", "T"]
                
                for i in xrange(0, len(word)):
                    for choice in choices:
                        newWord = word[:i] + choice + word[i + 1:]
                        if newWord in dict:
                            ret.append(newWord)
                return ret
            dict = {}
            q1 = deque([(start, 0)])
            q2 = deque([(end, 0)])
            for b in bank:
                if b in (start, end):
                    dict[b] = (b, 0)
                else:
                    dict[b] = (None, None)
            if end not in dict:
                return -1
                
            while q1 or q2:
                if q1:
                    word, dist = q1.popleft()
                    for nbr in getNeighbors(word, dict):
                        source, curDist = dict[nbr]
                        if source == start:
                            continue
                        if source is None:
                            dict[nbr] = start, dist + 1
                            q1.append((nbr, dist + 1))
                        if source == end:
                            return curDist + dist + 1
    
                if q2:
                    word, dist = q2.popleft()
                    for nbr in getNeighbors(word, dict):
                        source, curDist = dict[nbr]
                        if source == end:
                            continue
                        if source is None:
                            dict[nbr] = end, dist + 1
                            q2.append((nbr, dist + 1))
                        if source == start:
                            return curDist + dist + 1
                    
            return -1
                
    

Log in to reply
 

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