399. Evaluate Division 除法求值

@TOC

# 题目描述

Equations are given 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:

``````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 ].
``````

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 `vector<double>`.

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.

# 解题方法

Python代码如下：

``````class Solution:
def calcEquation(self, equations, values, queries):
"""
:type equations: List[List[str]]
:type values: List[float]
:type queries: List[List[str]]
:rtype: List[float]
"""
table = collections.defaultdict(dict)
for (x, y), value in zip(equations, values):
table[x][y] = value
table[y][x] = 1.0 / value
ans = [self.dfs(x, y, table, set()) if x in table and y in table else -1.0 for (x, y) in queries]
return ans

def dfs(self, x, y, table, visited):
if x == y:
return 1.0
for n in table[x]:
if n in visited: continue
d = self.dfs(n, y, table, visited)
if d > 0:
return d * table[x][n]
return -1.0
``````