Simple'n'Clean DFS solution in Python

  • 10

    A series of equations A / B = k can be seen as a graph in which nodes are the dividend and divisor A and B and weights are the result of the division. So we simply create the graph and traverse it with DFS/BFS to get our result.

    Complexity is K * O(N + M) where N and M are the number of nodes and edges, and K is the number of queries. How many nodes can we have? It's 2 * E, where E is the number of equations (2 different nodes per each equation). We can have at most E edges in the graph.

    So total complexity is O(K * E), with O(E) additional space for the graph.

    class Solution(object):
        def calcEquation(self, equations, values, queries):
            def dfs(start, end, path, paths):
                if start == end and start in G:
                    paths[0] = path
                if start in vis: 
                for node in G[start]:
                    dfs(node, end, path * W[start, node], paths)
            G, W = collections.defaultdict(set), collections.defaultdict(float)
            for (A, B), V in zip(equations, values):
                G[A], G[B] = G[A] | {B}, G[B] | {A}
                W[A, B], W[B, A] = V, 1.0 / V
            res = []
            for X, Y in queries:
                paths, vis = [-1.0], set()
                dfs(X, Y, 1.0, paths)
                res += paths[0],
            return res

  • 0

    I like your code! Clean and easy to understand.

Log in to reply

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