LeetCode 399. Evaluate Division

Description

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& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector.

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.

描述

```给定 a / b = 2.0, b / c = 3.0

```

```equations(方程式) = [ ["a", "b"], ["b", "c"] ],
values(方程式结果) = [2.0, 3.0],
queries(问题方程式) = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
```

思路

• 这道题可以转换为图来做。
• a / b = 2,b / c= 3,则 a / c = a / b * b / c。
• 令给定的表达式的除数与被除数为两个节点，链接这两个节点边的权重为表达式的值（ a / b = 2 => 可以形成两条边：a –> b = 2.0,b –> a == 0.5）。
• 为了求的 a / c 的值，就是找一条路径从 a 到 c，然后把所有边的权重乘起来。
• 使用深度优先搜索，找到满足条件的任意一条路径即可。
```# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-09-01 12:45:54

from typing import List
from collections import defaultdict

class Solution(object):

def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
graph = self.__build_graph(equations, values)
return list(map(lambda query: self.__query(graph, query[0], query[1], set()), queries))

def __build_graph(self, equations, values):
"""
构建图
"""
graph = defaultdict(dict)
for e, v in zip(equations, values):
root, node = e
graph[root][node] = v
graph[node][root] = 1 / v

return graph

def __query(self, garph, start, end, visited):

# 根据题中的描述，表达式中的字母必须出现在 equations 过
# 因此 x / x 不能返回 1，因为 x 没有出现过
if start not in garph and end not in garph:
return -1.0
if start == end:
return 1.0

for next_ in garph[start]:
if next_ in visited:
continue
tmp = self.__query(garph, next_, end, visited)
if tmp > -1:
return tmp * garph[start][next_]

return -1
```