Simple'n'Clean DFS solution in Python


  • 11

    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
                    return
                if start in vis: 
                    return
                vis.add(start)
                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
    G

    I like your code! Clean and easy to understand.


  • 0
    C

    I am new to python, and I am not very familiar with python bitwise operator. So how the operator "|" works here.
    Thank you.


Log in to reply
 

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