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.
class Solution: 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: return -1.0 visited = set() stack = collections.deque([(source, 1.0)]) while stack: front, current = stack.popleft() if front == target: return current visited.add(front) for back, value in graph[front]: if back not in visited: stack.append((back, current * value)) return -1.0 return [check(source, target) for (source, target) in queries]