LC 0399 [M] Evaluate Division - ALawliet/algorithms GitHub Wiki
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
# build graph
G = defaultdict(dict)
for (a, b), v in zip(equations, values):
G[a][b] = v
G[b][a] = 1/v
visited = set()
def dfs(a, b):
if a in visited:
return -1
if b in G[a]:
return G[a][b]
visited.add(a)
res = -1
for neighbor in G[a]:
res = dfs(neighbor, b)
if res != -1:
res *= G[a][neighbor]
break
visited.remove(a) # backtrack
return res
return [dfs(a, b) for a, b in queries]
class Solution(object):
def calcEquation(self, equations, values, queries):
G = defaultdict(dict)
for (a, b), v in zip(equations, values):
G[a][b] = v
G[b][a] = 1/v
def bfs(a, b):
if not (a in G and b in G):
return -1.0
Q = [ (a, 1.0) ]
visited = set()
for a, v in Q:
if a == b:
return v
visited.add(a)
for c in G[a]:
if c not in visited:
Q.append( (c, G[a][c]*v) )
return -1.0
return [bfs(a, b) for a, b in queries]