Python OO solution (42 ms) with some optimizations


  • 0

    A reasonably fast solution, which aims to make the logic fairly readable from the code using object oriented programming. The steps are simple:

    1. Build the digraph using the data given.
      • Nodes have variable names as values, and edges have numerical values.
      • For example, if we have [x]--(a)-->[y], this represents x/y = a.
      • Automatically add "inverse" edges to represent y/x = 1/a.
    2. For each (start, end) pair, perform a DFS beginning at start.
      • If a path is found, multiply every edge value along that path to get the answer.
      • To speed up future searches, add a connection representing that calculation to the digraph (as well as the inverse connection).

    For quick lookups, all lists of nodes are actually dictionaries, with variable names as keys and Node classes as values. Redundant, but quick!

    class Node(object):
        def __init__(self, name):
            self.name = name;
            self.outs = {};
    
        def addConnection(self, node, value):
            """ Create an edge with value "value", and an edge in the reverse direction with value 1/"value". """
            if node.name not in self.outs:
                self.outs[node.name] = (node, value)
            inverse = 1.0/value
            if inverse not in node.outs:
                node.outs[self.name] = (self, inverse)
    
        def dfs(self, end, visited = []):
            """ Attempts to find a path from this node to "end" nodes. """
            newvisited = visited + [self.name]
            if self.name == end:
                return newvisited
    
            for outnode in self.outs:
                if self.outs[outnode] [0].name not in visited:     # No loops in our path!
                    result = self.outs[outnode] [0].dfs(end, newvisited)
                    if result[-1] == end:   # Success was returned, continue to return it
                        return result
                # Otherwise continue through the outnodes.
    
            return newvisited
    
    class Digraph(object):
        def __init__(self, equations, values):
            """ Build a digraph with appropriate named nodes and weighted edges. """
            self.nodes = {}
    
            # Build the connections.
            for i in range(len(equations)):
                # Add 0, 1, or 2 nodes as needed
                eq = equations[i]
                if eq[0] not in self.nodes:
                    self.nodes[eq[0]] = Node(eq[0])
                if eq[1] not in self.nodes:
                    self.nodes[eq[1]] = Node(eq[1])
    
                # Add edges. (Automatically adds the inverse edge if it doesn't already exist.)
                self.nodes[eq[0]].addConnection(self.nodes[eq[1]], values[i])
    
        def multiplyPath(self, path):
            """ Takes a connected path of nodes and returns the product of their edges. """
            prod = 1
            for i in range(len(path)-1):
                prod *= self.nodes[path[i]].outs[ path[i+1] ] [1]
    
            return prod
    
    class Solution(object):
        def calcEquation(self, equations, values, queries):
            """
            :type equations: List[List[str]]
            :type values: List[float]
            :type queries: List[List[str]]
            :rtype: List[float]
            """
            # 1. Build the digraph
            dg = Digraph(equations, values)
            print "Built digraph:";
            print dg.display()
    
            # 2. Do a DFS for each query.
                # 2.5 to optimize, add each answer as an edge after it's computed.
            answer = []
            for (start, end) in queries:
                if start not in dg.nodes or end not in dg.nodes:
                    answer.append(-1)
                    continue
                    
                path = dg.nodes[start].dfs(end)
                if path[-1] == end:
                    prod = dg.multiplyPath(path)
                    answer.append(prod)
                    dg.nodes[start].addConnection(dg.nodes[end], prod)
                else:
                    answer.append(-1)
    
            return answer
    

Log in to reply
 

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