399. Evaluate Division

399. Evaluate Division

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: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries, where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<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.

----------------------

Solution #1, Graph dfs
O(n * m), n是graph大小，m是query的数量，应该可以用union-find来优化

class Solution {
    class Node {
        public String key;
        public Map<Node, Double> neighbors;
        public Node(String key) {
            this.key = key;
            neighbors = new HashMap<>();
        }
    }
    
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        Map<String, Node> graph = buildGraph(equations, values);
        
        int n = queries.length;
        double[] rt = new double[n];
        
        for (int i = 0; i < queries.length; i++) {
            rt[i] = dfs(graph, queries[i][0], queries[i][1], 1.0, new HashSet<String>());
        }
        
        return rt;
    }
    
    private double dfs(Map<String, Node> graph, String start, String end, double value, Set<String> visited) {
        if (!graph.containsKey(start) || !graph.containsKey(end) || visited.contains(start)) return -1.0;
        if (start.equals(end)) return value;
        
        visited.add(start);
        for (Map.Entry<Node, Double> entry : graph.get(start).neighbors.entrySet()) {
            double rt = dfs(graph, entry.getKey().key, end, value * entry.getValue(), visited);
            if (rt != -1.0) return rt;    
            
        }
        
        return -1.0;
    }
    
    private Map<String, Node> buildGraph(String[][] equations, double[] values) {
        Map<String, Node> graph = new HashMap<>();
        
        for (int i = 0; i < equations.length; i++) {
            String[] pair = equations[i];
            if (!graph.containsKey(pair[0])) {
                Node node = new Node(pair[0]);
                graph.put(pair[0], node);
            }
            
            if (!graph.containsKey(pair[1])) {
                Node node = new Node(pair[1]);
                graph.put(pair[1], node);
            }
            
            graph.get(pair[0]).neighbors.put(graph.get(pair[1]), values[i]);
            graph.get(pair[1]).neighbors.put(graph.get(pair[0]), 1 / values[i]);
        }
        
        return graph;
    }
}

Solution #2, Union Find，用被除数当作parent
ToDo: 加入UF本身的优化：size based

class Solution {
    
    class Node {
        public String key;
        public double val;
        public Node(String key) {
            this.key = key;
            val = 1;
        }
        
        public Node(String key, double val) {
            this.key = key;
            this.val = val;
        }
    }
    
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        
        Map<String, Node> map = new HashMap<>();
        Map<String, String> uf = new HashMap<>();
        for (int i = 0; i < equations.length; i++) {
            String[] pair = equations[i];
            if (!map.containsKey(pair[0])) {
                map.put(pair[0], new Node(pair[0]));
                uf.put(pair[0], pair[0]);
            }

            if (!map.containsKey(pair[1])) {
                map.put(pair[1], new Node(pair[1]));
                uf.put(pair[1], pair[1]);
            }

            Node parentOf1 = find(uf, map, pair[0]);
            Node parentOf2 = find(uf, map, pair[1]);

            if (!parentOf1.key.equals(parentOf2.key)) {
                uf.put(parentOf2.key, parentOf1.key);
                map.get(parentOf2.key).val = values[i] * parentOf1.val / parentOf2.val;
            }
        }

        double[] rt = new double[queries.length];
        for (int i = 0; i < queries.length; i++) {
            if (!map.containsKey(queries[i][0]) || !map.containsKey(queries[i][1])) {
                rt[i] = -1.0;
                continue;
            }

            Node p1 = find(uf, map, queries[i][0]);
            Node p2 = find(uf, map, queries[i][1]);
            if (p1.key.equals(p2.key)) {
                rt[i] = p2.val / p1.val;
            }else {
                rt[i] = -1.0;
            }
        }

        return rt;
    }
        
    private Node find(Map<String, String> uf, Map<String, Node> map, String key) {
        String ori = key;
        double val = map.get(ori).val;

        while (!uf.get(key).equals(key)) {
            val *= map.get(uf.get(key)).val;
            key = uf.get(key);
        }

        uf.put(ori, key);
        map.get(ori).val = val;
        return new Node(key, val); // Use Node as Pair: return the key of parent, but the value of the original passed in key
    }
}