# LC 399. Evaluate Division

### [Problem link](https://leetcode.com/problems/evaluate-division/)

###### tags: `leedcode` `python` `medium` `DFS`

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

You are also given some <code>queries</code>, where <code>queries[j] = [C_j, D_j]</code> represents the <code>j^th</code> query where you must find the answer for <code>C_j / D_j = ?</code>.

Return the answers to all queries. If a single answer cannot be determined, return <code>-1.0</code>.

**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.

**Note:** The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.

**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 ]
note: x is undefined => -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:**

- <code>1 <= equations.length <= 20</code>
- <code>equations[i].length == 2</code>
- <code>1 <= A_i.length, B_i.length <= 5</code>
- <code>values.length == equations.length</code>
- <code>0.0 < values[i] <= 20.0</code>
- <code>1 <= queries.length <= 20</code>
- <code>queries[i].length == 2</code>
- <code>1 <= C_j.length, D_j.length <= 5</code>
- <code>A_i, B_i, C_j, D_j</code> consist of lower case English letters and digits.

## Solution 1 - DFS

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        graph = defaultdict(dict)
        for (x, y), val in zip(equations, values):
            graph[x][y] = val
            graph[y][x] = 1 / val

        def dfs(x, y, seen):
            if x not in graph or y not in graph:
                return -1

            if y in graph[x]:
                return graph[x][y]

            for i in graph[x].keys():
                if i in seen:
                    continue
                seen.add(i)
                tmp = dfs(i, y, seen)
                if tmp == -1:
                    continue
                return graph[x][i] * tmp

            return -1

        res = []
        for x, y in queries:
            res.append(dfs(x, y, set()))

        return res
        

>### Complexity
>n = equations.length = values.length
>m = queries.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(nm) | O(n) |

## Note
x