# Python simple AC Solution - using dict of dicts

• 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.

• 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

``````

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

• @WKVictor good solution~ it's elegant

• @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]
``````

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

• ``````    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]
``````

• 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

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