Python BFS 77%

  • 0

    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()
                while queue != []:
                    preUp, preValue = queue.pop(0)
                    for child in graph[preUp]:
                        if child in visited: continue
                        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.