399. Evaluate Division

;  |     Back to Homepage   |     Back to Code List


public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
    Map<String, Map<String, Double>> g = new HashMap<>();
    buildGraph(g, equations, values);

    double[] res = new double[queries.size()];
    Arrays.fill(res, -1.0);

    int index = 0;
    for (List<String> q : queries) {
        String a = q.get(0);
        String b = q.get(1);

        if (!g.containsKey(a) || !g.containsKey(b)) {
            index++;
            continue;
        } else {
            dfs(g, a, b, res, index, new HashSet<>(), 1.0);
            index++;
        }
    }

    return res;
}

private void dfs(Map<String, Map<String, Double>> g, String a, String b, double[] res, int index, Set<String> visited, double tmp) {
    visited.add(a);

    if (g.get(a) == null || g.get(a).size() == 0) {
        return;
    }

    if (g.get(a).containsKey(b)) {
        res[index] = g.get(a).get(b) * tmp;
        return;
    }

    for (String next : g.get(a).keySet()) {
        if (visited.contains(next)) continue;
        dfs(g, next, b, res, index, visited, g.get(a).get(next) * tmp);
    }
}

private void buildGraph(Map<String, Map<String, Double>> g, List<List<String>> equations, double[] values) {
    int index = 0;
    for (List<String> e : equations) {
        String a = e.get(0);
        String b = e.get(1);
        g.putIfAbsent(a, new HashMap<>());
        g.putIfAbsent(b, new HashMap<>());
        g.get(a).put(b, values[index]);
        g.get(b).put(a, 1.0 / values[index]);
        index++;
        g.get(a).put(a, 1.0);
        g.get(b).put(b, 1.0);
    }
}