Evaluate Division

1package pkg5leetcode.interview150;2 3/*4 * Evaluate Division | LC 3995 * APPROACH: Build weighted graph; DFS/BFS to find quotient path.6 * COMPLEXITY: Time O(q*(V+E)), Space O(V+E)7 */8import java.util.*;9 10public class interview150_LC399EvaluateDivision {11    static double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {12        Map<String, Map<String, Double>> g = new HashMap<>();13        for (int i = 0; i < equations.size(); i++) {14            String a = equations.get(i).get(0), b = equations.get(i).get(1);15            g.computeIfAbsent(a, k -> new HashMap<>()).put(b, values[i]);16            g.computeIfAbsent(b, k -> new HashMap<>()).put(a, 1.0 / values[i]);17        }18        double[] res = new double[queries.size()];19        for (int i = 0; i < queries.size(); i++) {20            String x = queries.get(i).get(0), y = queries.get(i).get(1);21            if (!g.containsKey(x) || !g.containsKey(y)) res[i] = -1.0;22            else res[i] = dfs(x, y, g, new HashSet<>());23        }24        return res;25    }26 27    static double dfs(String cur, String target, Map<String, Map<String, Double>> g, Set<String> seen) {28        if (cur.equals(target)) return 1.0;29        seen.add(cur);30        for (Map.Entry<String, Double> e : g.get(cur).entrySet()) {31            if (!seen.contains(e.getKey())) {32                double d = dfs(e.getKey(), target, g, seen);33                if (d > 0) return e.getValue() * d;34            }35        }36        return -1.0;37    }38 39    public static void main(String[] args) {40        List<List<String>> eq = Arrays.asList(41            Arrays.asList("a", "b"), Arrays.asList("b", "c"));42        double[] val = {2.0, 3.0};43        List<List<String>> q = Arrays.asList(44            Arrays.asList("a", "c"), Arrays.asList("b", "a"), Arrays.asList("a", "e"));45        double[] r = calcEquation(eq, val, q);46        check(r[0] == 6.0, "case1");47        check(r[1] == 0.5, "case2");48        check(r[2] == -1.0, "case3");49        System.out.println("all tests passed");50    }51 52    static void check(boolean cond, String name) {53        if (!cond) throw new AssertionError("FAILED: " + name);54        System.out.println("  PASS " + name);55    }56}