Evaluate Division

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