## Description

https://leetcode.com/problems/most-common-word/

You are given an array of variable pairs `equations`

and an array of real numbers `values`

, where `equations[i] = [A`

and _{i}, B_{i}]`values[i]`

represent the equation `A`

. Each _{i} / B_{i} = values[i]`A`

or _{i}`B`

is a string that represents a single variable._{i}

You are also given some `queries`

, where `queries[j] = [C`

represents the _{j}, D_{j}]`j`

query where you must find the answer for ^{th}`C`

._{j} / D_{j} = ?

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.0queries 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 <= A`

_{i}.length, B_{i}.length <= 5`values.length == equations.length`

`0.0 < values[i] <= 20.0`

`1 <= queries.length <= 20`

`queries[i].length == 2`

`1 <= C`

_{j}.length, D_{j}.length <= 5`A`

consist of lower case English letters and digits._{i}, B_{i}, C_{j}, D_{j}

## Explanation

dfs

## Python Solution

```
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
graph = collections.defaultdict(list)
for equation, value in zip(equations, values):
numerator, denominator = equation[0], equation[1]
graph[numerator].append((denominator, value))
graph[denominator].append((numerator, 1 / value))
result = []
for numerator, denominator in queries:
visited = set()
value = self.helper(graph, numerator, denominator, visited)
result.append(value)
return result
def helper(self, graph, numerator, denominator, visited):
if numerator not in graph:
return -1.0
if numerator == denominator:
return 1.0
visited.add(numerator)
for neighbor, value in graph[numerator]:
if neighbor == denominator:
return value
if neighbor not in visited:
quotient = self.helper(graph, neighbor, denominator, visited)
if quotient != -1:
return value * quotient
return -1.0
```

- Time Complexity: ~NM
- Space Complexity: ~N

Let N be the number of input equations and M be the number of queries.