Equations are given in the format
A / B = k, where
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
a / b = 2.0, b / c = 3.0.
a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
[6.0, 0.5, -1.0, 1.0, -1.0 ].
The input is:
vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where
equations.size() == values.size(), and the values are positive. This represents the equations. Return
According to the example above:
equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
graph = dict()
# Build graph
for (a, b), value in zip(equations, values):
graph[a] = graph.get(a, ) + [(b, value)]
graph[b] = graph.get(b, ) + [(a, 1/value)]
def check(source, target):
# If there is any one number of the query didn't appear in the graph, answer certainly doesn't exist.
if source not in graph or target not in graph:
visited = set()
stack = collections.deque([(source, 1.0)])
front, current = stack.popleft()
if front == target:
for back, value in graph[front]:
if back not in visited:
stack.append((back, current * value))
return [check(source, target) for (source, target) in queries]