> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Evaluate Division Python Solution with Tests

> Tested Python solution for LeetCode 399 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 399, Medium. Topics: Array, String, Depth-First Search, Breadth-First Search, Union-Find, Graph Theory, Shortest Path. [View on LeetCode](https://leetcode.com/problems/evaluate-division/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 399   # by problem number
lcpy gen -s evaluate_division   # by problem name
```

## Problem

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.

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

### Examples

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

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

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

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/evaluate_division/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/evaluate_division/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O((V + E) * Q) where V = variables, E = equations, Q = queries
    # Space: O(V + E) for the graph
    def calc_equation(
        self, equations: list[list[str]], values: list[float], queries: list[list[str]]
    ) -> list[float]:
        # Build weighted graph: adj[a][b] = a / b
        graph: dict[str, dict[str, float]] = {}
        for (a, b), value in zip(equations, values, strict=True):
            graph.setdefault(a, {})[b] = value
            graph.setdefault(b, {})[a] = 1.0 / value

        def bfs(start: str, target: str) -> float:
            if start not in graph or target not in graph:
                return -1.0
            if start == target:
                return 1.0
            queue = [(start, 1.0)]
            seen = {start}
            for node, product in queue:
                for neighbor, weight in graph[node].items():
                    if neighbor == target:
                        return product * weight
                    if neighbor not in seen:
                        seen.add(neighbor)
                        queue.append((neighbor, product * weight))
            return -1.0

        return [bfs(c, d) for c, d in queries]
```

## Complexity

| Time                                                            | Space                  |
| --------------------------------------------------------------- | ---------------------- |
| O((V + E) \* Q) where V = variables, E = equations, Q = queries | O(V + E) for the graph |

## Tags

[NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).