399 Evaluate Division

399. Evaluate Division

1. Question

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

Example: Givena / 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:vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries, whereequations.size() == values.size(), and the values are positive. This represents the equations. Returnvector<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"] ].

2. Implementation

(1) Union Find

思路: 用union find的思路主要是将 a/b公式中的分母(在这里是b)作为分子的parent, 如果我们知道a/b, 和b/c的值，则要查询a/c时，我们只需要知道a和c在union find里的root, 如果他们有共同的root, 则有解，否则无解。我觉得union find的解法，关键是如何设置node的parent，通过代码可以发现，我们将node b设为node a的parent当:

• a和b都不在图中，而b是equation中的分母，a是对应的分子

• b已经出现在图中，而a不在

• 如果a和b都在图中，找出a和b对应的root，将a的root的parent设为b的root的parent

class Solution {
    class Node {
        String parent;
        double ratio;

        public Node(String parent, double ratio) {
            this.parent = parent;
            this.ratio = ratio;
        }
    }

    class UnionFind {
        Map<String, Node> nodes = new HashMap();

        public Node find(String s) {
            if (!nodes.containsKey(s)) {
                return null;
            }

            Node curNode = nodes.get(s);

            if (!curNode.parent.equals(s)) {
                Node parentNode = find(curNode.parent);
                curNode.parent = parentNode.parent;
                curNode.ratio *= parentNode.ratio;
            }
            return curNode;
        }

        public void union(String a, String b, double ratio) {
            boolean hasA = nodes.containsKey(a);
            boolean hasB = nodes.containsKey(b);

            if (!hasA && !hasB) {
                nodes.put(a, new Node(b, ratio));
                nodes.put(b, new Node(b, 1.0));
            }
            else if (!hasA) {
                nodes.put(a, new Node(b, ratio));
            }
            else if (!hasB) {
                nodes.put(b, new Node(a, 1.0 / ratio));
            }
            else {
                Node rootA = find(a);
                Node rootB = find(b);
                rootA.parent = rootB.parent;
                rootA.ratio = ratio / rootA.ratio * rootB.ratio;
            }
        }
    }
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        UnionFind uf = new UnionFind();

        for (int i = 0; i < equations.length; i++) {
            uf.union(equations[i][0], equations[i][1], values[i]);
        }

        double[] res = new double[queries.length];

        for (int i = 0; i < queries.length; i++) {
            Node rootX = uf.find(queries[i][0]);
            Node rootY = uf.find(queries[i][1]);

            if (rootX == null || rootY == null || !rootX.parent.equals(rootY.parent)) {
                res[i] = -1.0;
            }
            else {
                res[i] = rootX.ratio / rootY.ratio;
            }
        }
        return res;
    }
}

(2) DFS

class Solution {
    class Edge {
        String val;
        double weight;

        public Edge(String val, double weight) {
            this.val = val;
            this.weight = weight;
        }
    }


    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        double[] res = new double[queries.length];

        if (equations == null || equations.length == 0) {
            return res;
        }

        Map<String, List<Edge>> graph = new HashMap();

        for (int i = 0; i < equations.length; i++) {
            String[] equation = equations[i];
            String vertex1 = equation[0];
            String vertex2 = equation[1];

            graph.putIfAbsent(vertex1, new ArrayList());
            graph.get(vertex1).add(new Edge(vertex2, values[i]));

            graph.putIfAbsent(vertex2, new ArrayList());
            graph.get(vertex2).add(new Edge(vertex1, 1/values[i]));
        }

        for (int i = 0; i < queries.length; i++) {
            String start = queries[i][0];
            String end = queries[i][1];

            Set<String> visited = new HashSet();
            dfs(start, end, 1.0, i, visited, graph, res);

            if (res[i] == 0 && !start.equals(end)) {
                res[i] = -1.0;
            }
        }
        return res;
    }

    public void dfs(String start, String end, double value, int index, Set<String> visited, Map<String, List<Edge>> graph, double[] res) {
        if (!graph.containsKey(start) || !graph.containsKey(end)) {
            res[index] = -1.0;
            return;
        }


        if (start.equals(end)) {
            res[index] = value;
            return;
        }

        if (visited.contains(start)) {
            return;
        }

        visited.add(start);
        for (Edge edge : graph.get(start)) {
            dfs(edge.val, end, value * edge.weight, index, visited, graph, res);
        }
    }
}

3. Time & Space Complexity

(1) Union Find: 时间复杂度O(e + q), 创建union find需要O(e)时间, e是equations的长度, 每次query的需要O(1)时间，所以总的query时间是O(q), 两部分加起来是O(e + q), 空间复杂度O(e)， 空间主要是创建Union Find时，用到的map需要node的个数

(2) DFS: 时间复杂度(e + q*e), O(e)