Shailesh Kumar

Posted on

# Evaluate Division | Leetcode Day 24

Problem -

You are given equations in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating-point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example

``````Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
``````

Intution - Find the path from source to destination, multiply the edge weights
Solution -

``````from collections import defaultdict
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
g = defaultdict(list)
for i in range(len(equations)):
eq = equations[i]
val = values[i]
s, d = eq
g[s].append((d, val))
g[d].append((s, 1/val))
# print(g)
def dfs(root, path, s, d):
nonlocal st
path = path + [root]
if s in st and d in st:
return path
res = None
for child in g.get(root[0], []):
if child[0] not in st:
res =  dfs(child, path, s, d)
if res is not None:
return res
ans = []
for s, d in queries:
if s == d:
if s in g:
ans.append(1)
else:
ans.append(-1)
continue
st = set()
path = dfs((s, 1), [], s, d)
if path is None:
st = set()
path = dfs((d, 1), [], s, d)
if path is None:
ans.append(-1)
else:
flag = False
res = 1
id_p = [el[0] for el in path]
s_i = id_p.index(s)
e_i = id_p.index(d)
if s_i <= e_i:
for i in range(s_i + 1, e_i + 1):
res*= path[i][1]
ans.append(res)
else:
for i in range(s_i, e_i, -1):
res *= 1/path[i][1]
ans.append(res)
return ans
``````