399. Evaluate Division

Leetcode Graph

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:

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

The input is: String[][] equations, double[] values, String[][] queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return double[].

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

分析

这道题目的难点在于发现可以用图论解决。对于方程A/B = C，可以把A、B视为图的节点，AB构成图的一条边，C为边的权重。以这种方式构建有向图，那么对于任意方程x/y的问题可以转化为在有向图中，是否存在一条路径$x-y$，如果存在则返回路径的权重。可以用DFS解决，时间复杂度为$O(Q\times(E+V))$，其中$Q$为查询的数量，$E$为方程数量，$V$为方程中字母的数量。

public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
    if (equations == null || values == null || queries == null) return new double[]{};
    // construct graph
    Map<String, Map<String, Double>> graph = new HashMap<>(); // graph
    for (int i = 0; i < equations.length; i++) {
        String v = equations[i][0], w = equations[i][1];
        if (!graph.containsKey(v)) graph.put(v, new HashMap<>());
        if (!graph.containsKey(w)) graph.put(w, new HashMap<>());
        graph.get(v).put(w, values[i]);
        graph.get(w).put(v, 1.0/values[i]);
    }
    Set<String> mark = new HashSet<>();;
    Map<String, Double> distTo = new HashMap<>();;
    double[] res = new double[queries.length];
    for (int i = 0; i < queries.length; i++) {
        String v = queries[i][0], w = queries[i][1];
        // invalid query
        if (!graph.containsKey(v) || !graph.containsKey(w)) {
            res[i] = -1.0;  continue; }
        // clear dfs result
        if (i > 0) { distTo.clear(); mark.clear();}

        // start dfs
        distTo.put(v, 1.0);
        dfs(graph, mark, distTo, v);

        // check result
        if (!mark.contains(w)) res[i] = -1.0;
        else res[i] = distTo.get(w);
    }
    return res;
}

private void dfs(Map<String, Map<String, Double>> graph, Set<String> mark,
                 Map<String, Double> distTo, String v) {
    mark.add(v);
    for (String w: graph.get(v).keySet()) {
        if (!mark.contains(w)) {
            distTo.put(w, distTo.get(v)*graph.get(v).get(w));
            dfs(graph, mark, distTo, w);
        }
    }
}