Python simple AC Solution - using dict of dicts


  • 3

    This code could be more concise.

    1. Put every number into a two-layer dictionary to record it's multiply.
    2. For each query pair, check whether they're in the dictionary or not.
      If both exist => solution must exist.
    3. Record the multiply and the number we've visited already, keep seeking the dictionary until find out the solution.

    For example:
    equation = [["a","e"],["b","e"]], value = [4,3], query = [["a", "b"]]

    1. Construct a dictionary = {"a": {"a":1, "e":4}, "b": {"b":1, "e":3}, "e": {"a": 1/4, "b": 1/3} }
    2. Follow the path: dct["a"] => dct["e"] => dct["b"], we have query [["a", "b"]] = 4 x 1/3 = 4/3
    class Solution(object):
        def calcEquation(self, equations, values, query):
        	def seeker(a, b, path=[]):
        		# seek the result of a/b
        		if a not in dct.keys() or b not in dct.keys():      # No solution
        			return 0
        		if b in dct[a]:                       # This is it!
        			return dct[a][b]
        		else:                                 # Keep looking for solution
        			tmp = []
        			for c in dct[a].keys():
        				if c not in path and (seeker(c, b, path+[c])):
        					return dct[a][c]*(seeker(c, b, path+[c]))
    
            dct = {}                              # Put every number into the dict
            for i in xrange(len(equations)):
            	nums = equations[i]
            	div = float(values[i])
            	if nums[0] in dct.keys():
            		dct[nums[0]][nums[1]] = div
            	else:
            		dct[nums[0]] = {nums[0]:1, nums[1]:div}
            	if nums[1] in dct.keys():
            		dct[nums[1]][nums[0]] = 1.0/div
            	else:
            		dct[nums[1]] = {nums[1]:1, nums[0]:1.0/div}
    
            res = []
            for pair in query:                    # seek the solution
            	if seeker(pair[0], pair[1]):
            		res += seeker(pair[0], pair[1]),
            	else:
            		res += -1,
    
            return [float(n) for n in res]
    

    EDIT:
    Thanks to @WKVictor 's simplification, it improved from 45ms -> 32ms.


  • 5
    W

    Nice solution! I simplified your code to the following code (32ms):

    class Solution(object):
        def calcEquation(self, equations, values, query):
            """
            :type equations: List[List[str]]
            :type values: List[float]
            :type query: List[List[str]]
            :rtype: List[float]
            """
            # Build directed graph
            graph = collections.defaultdict(dict)   # adjacency list (dict of dicts)
            for edge, val in zip(equations, values):
                graph[edge[0]][edge[1]], graph[edge[1]][edge[0]] = val, 1.0/val   # weight of directed edges
                graph[edge[0]][edge[0]], graph[edge[1]][edge[1]] = 1.0, 1.0    # weight of self loop
                
            return [self.dfs(graph, q[0], q[1], []) for q in query]
                
            
        def dfs(self, graph, start, end, path):
            if start not in graph or end not in graph:
                return -1.0       # if none of the nodes exists, return -1.0
            if end in graph[start]:
                return graph[start][end]    # got it! 
            else:
                for node in graph[start]:
                    if node not in path:    # avoid being trapped in loop
                        val = self.dfs(graph, node, end, path+[node])
                        if val != -1.0:
                            return graph[start][node] * val
                return -1.0    # means no such path from start to end exists
            
    

  • 0

    @WKVictor Thank you. The usage of collections.defaultdict(dict) is amazing!


  • 0

    @WKVictor good solution~ it's elegant


  • 0
    C

    @WKVictor You can do memoization before you return.

    if node not in path:    # avoid being trapped in loop
        val = self.dfs(graph, node, end, path+[node])
        if val != -1.0:
            graph[start][end] = graph[start][node] * val
            return graph[start][end]
    

  • 0
    W

    @cqnkxy Good catch! It saves ~10ms. Thanks!


  • 0
    D
        def calcEquation(self, equations, values, queries):
            def dfs(a, b, visited):
                if b in mem[a]:
                    return mem[a][b]
                for c in mem[a].keys():
                    if c not in visited:
                        v = dfs(c, b, visited + [c])
                        if v != -1.0:
                            return mem[a][c] * v
                return -1.0
            mem = collections.defaultdict(dict)
            for i, pair in enumerate(equations):
                a, b, v = pair[0], pair[1], values[i]
                mem[a][b], mem[b][a] = v, 1/v
                mem[a][a], mem[b][b] = 1.0, 1.0
            return [dfs(q[0], q[1], []) if mem[q[0]] and mem[q[1]] else -1.0 for q in queries]
    

  • 0
    Z

    Our solution almost identical! I think it would make more sense to call "two-layer dictionary" as adjacency list.

    https://discuss.leetcode.com/topic/77373/python-35ms-dfs


Log in to reply
 

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