# 0399. Evaluate Division

<https://leetcode.com/problems/evaluate-division>

## Description

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.

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

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

## ac

```java
class Solution {
    Map<String, Double> value;
    Map<String, Set<String>> graph;
    Set<String> visiting;

    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        // edge cases
        // illegal arguments

        value = new HashMap<>();
        // build graph
        graph = new HashMap<>();
        for (int i = 0; i < equations.length; i++) {
            String[] e = equations[i];
            if (!graph.containsKey(e[0])) graph.put(e[0], new HashSet<String>());
            if (!graph.containsKey(e[1])) graph.put(e[1], new HashSet<String>());
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
            // store value
            value.put(e[0]+e[1], values[i]);
            value.put(e[1]+e[0], 1.0 / values[i]);
        }

        // dfs find path, get result
        visiting = new HashSet<String>();
        double[] res = new double[queries.length];
        for (int i = 0; i < queries.length; i++) {
            String[] q = queries[i];
            double tmp = dfs(q[0], q[1]);
            res[i] = tmp;
        }

        return res;
    }

    private double dfs(String from, String to) {
        // exit
        if (!graph.containsKey(from)) return -1.0;
        if (from.equals(to)) return 1.0;

        visiting.add(from);
        double res = -1.0;

        // look around
        for (String next : graph.get(from)) {
            if (visiting.contains(next)) continue;
            // if (next.equals(to)) {
            //     res = value.get(from+next);
            //     break;
            // } else {
                double tmp = dfs(next, to);
                if (tmp != -1.0) {
                    res = value.get(from+next) * tmp;
                }
            // }
        }

        visiting.remove(from);
        return res;
    }
}

/*
map store value
dfs find path
*/
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/solutions/0399-evaluate-division.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.