[Leetcode] Problem 399 - Evaluate Division

Posted on | In ,

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

No.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]

No.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]

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
private Map<String, List<Object>> parent = new HashMap<>();

public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
    double[] result = new double[queries.size()];
    
    for (int i = 0; i < equations.size(); i++) {
        String a = equations.get(i).get(0);
        String b = equations.get(i).get(1);
        double value = values[i];

        if (!parent.containsKey(a) && !parent.containsKey(b)) {
            parent.put(a, Arrays.asList(b, value));
            parent.put(b, Arrays.asList(b, 1.0));
        } else if (!parent.containsKey(a)) {
            parent.put(a, Arrays.asList(b, value));
        } else if (!parent.containsKey(b)) {
            parent.put(b, Arrays.asList(a, 1.0 / value));
        } else {
            List<Object> parentA = findParent(a); // a/pa
            List<Object> parentB = findParent(b); // b/pb
            // pa/pb = a/b * (b/pb) / (a/pa) 
            parent.put((String) parentA.get(0), Arrays.asList(parentB.get(0), value * (double) parentB.get(1) / (double) parentA.get(1)));
        }
    }

    for (int i = 0; i < queries.size(); i++) {
        String a = queries.get(i).get(0);
        String b = queries.get(i).get(1);

        if (!parent.containsKey(a) || !parent.containsKey(b)) {
            result[i] = -1.0;
            continue;
        }

        List<Object> parentA = findParent(a); // a/c
        List<Object> parentB = findParent(b); // b/c

        if (!parentA.get(0).equals(parentB.get(0)))
            result[i] = -1.0;
        else
        // a/b = (a/c) / (b/c)
            result[i] = (double) parentA.get(1) / (double) parentB.get(1);
    }

    return result;
}

private List<Object> findParent(String node) {
    double value = 1.0;

    while (!node.equals(parent.get(node).get(0))) {
        value *= (double) parent.get(node).get(1);
        node = String.valueOf(parent.get(node).get(0));
    }

    return Arrays.asList(node, value);
}