Python BFS 77%


  • 0
    F

    Another BFS solution

        def calcEquation(self, equations, values, queries):
            
            graph = collections.defaultdict(dict)
            
            # make graph
            for (up, down), val in zip(equations, values):
                graph[up][down] = val
                graph[down][up] = 1/val
                graph[up][up] = graph[down][down] = 1.0
            
            # using BFS
            def bfs(up, down):
                if up not in graph: return -1.0
                if down in graph[up]: return graph[up][down]
                
                queue = [(up, 1)]
                visited = set()
                visited.add(up)
                
                while queue != []:
                    preUp, preValue = queue.pop(0)
                    for child in graph[preUp]:
                        if child in visited: continue
                        visited.add(child)
                        v = graph[preUp][child]*preValue
                        if child == down: return v
                        queue.append((child, v))
                return -1.0
            
            return [ bfs(up,down) for up, down in queries]
    

Log in to reply
 

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