You are given an array of variable pairs  `equations`  and an array of real numbers  `values` , where  `equations[i] = [Ai, Bi]`  and  `values[i]`  represent the equation  `Ai / Bi = values[i]` . Each  `Ai`  or  `Bi`  is a string that represents a single variable.

You are also given some  `queries` , where  `queries[j] = [Cj, Dj]` represents the  `jth`  query where you must find the answer for  `Cj / Dj = ?` .

Return the answers to all queries. If a single answer cannot be determined, return  `-1.0` .

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Example 1:

```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]
Explanation:
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]
```

Example 2:

```Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]
```

Example 3:

```Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]
```

Constraints:

• `1 <= equations.length <= 20`
• `equations[i].length == 2`
• `1 <= Ai.length, Bi.length <= 5`
• `values.length == equations.length`
• `0.0 < values[i] <= 20.0`
• `1 <= queries.length <= 20`
• `queries[i].length == 2`
• `1 <= Cj.length, Dj.length <= 5`
• `Ai, Bi, Cj, Dj`  consist of lower case English letters and digits.

Solution:

For example:
Given:
a/b = 2.0, b/c = 3.0
We can build a directed graph:
a — 2.0 –> b — 3.0 –> c
If we were asked to find a/c, we have:
a/c = a/b * b/c = 2.0 * 3.0
In the graph, it is the product of costs of edges.

Do notice that, 2 edges need to added into the graph with one given equation,
because with a/b we also get result of b/a, which is the reciprocal of a/b.

so the previous example also gives edges:
c — 0.333 –> b — 0.5 –> a

Now we know how to model this problem, what we need to do is simply build the
graph with given equations, and traverse the graph, either DFS or BFS, to find a path
for a given query, and the result is the product of costs of edges on the path.

One optimization, which is not implemented in the code, is to “compress” paths for
past queries, which will make future searches faster. This is the same idea used in
compressing paths in union find set. So after a query is conducted and a result is found,
we add two edges for this query if these edges are not already in the graph.

Given the number of variables N, and number of equations E,
building the graph takes O(E), each query takes O(N), space for graph takes O(E)

I think if we start to compress paths, the graph will grow to O(N^2), and we
can optimize the query to O(1), please correct me if I’m wrong.

``````class Solution(object):
def calcEquation(self, equations, values, queries):
graph = {}
def build_graph(equations, values):
if f in graph:
graph[f].append((t, value))
else:
graph[f] = [(t, value)]
for vertices, value in zip(equations, values):
f, t = vertices
def find_path(query):
b, e = query
if b not in graph or e not in graph:
return -1.0
q = collections.deque([(b, 1.0)])
visited = set()
while q:
front, cur_product = q.popleft()
if front == e:
return cur_product
for neighbor, value in graph[front]:
if neighbor not in visited:
q.append((neighbor, cur_product*value))
return -1.0
build_graph(equations, values)
return [find_path(q) for q in queries]``````
Categories: InterviewPython

Article Rating
Subscribe
Notify of 