# python solution without graph search, beat 98%

• My code does not use graph search. Instead, my idea is simple, for a/b=k1, b/c=k2, I build a map where b = 1, a = b*k1, c = b/k2 ...

``````    def calcEquation(self, equations, values, queries):
"""
:type equations: List[List[str]]
:type values: List[float]
:type queries: List[List[str]]
:rtype: List[float]
"""
assert len(equations) > 0
graphs = []
remaining = range(len(equations))
m = {}

while len(remaining) > 0:
next = set()
for i in remaining:
x, y = equations[i]
if len(m) == 0:
m[y] = 1.0
if x in m:
assert y not in m
m[y] = m[x]/values[i]
elif y in m:
assert x not in m
m[x] = m[y]*values[i]
else:
if len(next) == len(remaining):
graphs.append(m)
m = {}
remaining = next
else:
graphs.append(m)

result = []
for q in queries:
x, y = q
for m in graphs:
if x in m and y in m:
result.append(m[x]/m[y])
break
else:
result.append(-1.0)
return result
``````

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