

399. Evaluate Division

Description

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

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

Java(DFS)

Map<String, Map<String, Double>> map;
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
    map = new HashMap<>();
    for(int i = 0; i < equations.length; i++) {
        String x = equations[i][0];
        String y = equations[i][1];
        double value = values[i];
        map.putIfAbsent(x, new HashMap<String, Double>());
        map.putIfAbsent(y, new HashMap<String, Double>());

        map.get(x).put(y, value);
        map.get(y).put(x, 1.0 / value);
    }
    double[] res = new double[queries.length];
    for(int i = 0; i < queries.length; i++) {
        if(!map.containsKey(queries[i][0]) || !map.containsKey(queries[i][0])) res[i] = -1.0;
        else res[i] = dfs(queries[i][0], queries[i][1], new HashSet<String>());
    }
    return res;
}
double dfs(String cur, String target, Set<String> set) {
    if(cur.equals(target)) return 1.0;
    set.add(cur);
    if(!map.containsKey(cur)) return -1.0;
    for(String neighbor : map.get(cur).keySet()) {
        if(set.contains(neighbor)) continue;
        double t = dfs(neighbor, target, set);
        if(t > -1.0) return t * map.get(cur).get(neighbor);
    }
    return -1.0;
}

Java(Union Find)

class Node{
    String parent;
    double ratio;
    Node(String parent, double ratio) {
        this.parent = parent;
        this.ratio = ratio;
    }
}
class UnionFindSet{
    Map<String, Node> parents = new HashMap<>();
    Node find(String s) {
        if(!parents.containsKey(s)) return null;
        Node n = parents.get(s);
        if(!n.parent.equals(s)) {
            Node t = find(n.parent);
            n.parent = t.parent;
            n.ratio *= t.ratio;
        }
        return n;
    }
    void union(String s, String p, double ratio) {
        boolean hasS = parents.containsKey(s);
        boolean hasP = parents.containsKey(p);
        if(!hasS && !hasP) {
            parents.put(s, new Node(p, ratio));
            parents.put(p, new Node(p, 1.0));
        }else if(!hasP){
            parents.put(p, new Node(s, 1.0 / ratio));
        }else if(!hasS) {
            parents.put(s, new Node(p, ratio));
        }else{
            Node pS = find(s);
            Node pP = find(p);
            pS.parent = pP.parent;
            pS.ratio = ratio / pS.ratio * pP.ratio;
        }
    }
}
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
    UnionFindSet uf = new UnionFindSet();
    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 root_x = uf.find(queries[i][0]), root_y = uf.find(queries[i][1]);
        if(root_x == null || root_y == null || !root_x.parent.equals(root_y.parent)) res[i] = -1.0;
        else res[i] = root_x.ratio / root_y.ratio;
    }
    return res;
}

Java(Floyd Warshall Algorithm)

public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
    HashMap<String, HashMap<String, Double>> graph = new HashMap<>();
    for(int i = 0; i < equations.length; i++) {
        graph.computeIfAbsent(equations[i][0], f -> new HashMap<>()).put(equations[i][1], values[i]);
        graph.computeIfAbsent(equations[i][1], f -> new HashMap<>()).put(equations[i][0], 1.0 / values[i]);
    }
    for(String mid : graph.keySet()) {
        for(String src : graph.get(mid).keySet()) {
            for(String dest : graph.get(mid).keySet()) {
                double val = graph.get(src).get(mid) * graph.get(mid).get(dest);
                graph.get(src).put(dest, val);
            }
        }
    }
    double[] res = new double[queries.length];
    for(int i = 0; i < queries.length; i++) {
        if(!graph.containsKey(queries[i][0])) res[i] = -1.0;
        else res[i] = graph.get(queries[i][0]).getOrDefault(queries[i][1], -1.0);
    }
    return res;
}

JavaScript

var calcEquation = function(equations, values, queries) {
    var map = new Map(),
        valueMap = new Map();
    for(let i = 0; i < equations.length; i++) {
        let x = equations[i][0];
        let y = equations[i][1];
        let v = values[i];
        if(!map.has(x)) {
            map.set(x, []);
            valueMap.set(x, [])
        }
        if(!map.has(y)) {
            map.set(y, []);
            valueMap.set(y, []);
        }
        map.get(x).push(y);
        map.get(y).push(x);
        valueMap.get(x).push(v);
        valueMap.get(y).push(1.0 / v);
    }
    var res = [];
    for(let j = 0 ; j < queries.length; j++) {
        let x = queries[j][0];
        let y = queries[j][1];
        if(!map.has(x) || !map.has(y)) {
            res.push(-1.0);
            continue;
        }
        res.push(dfs(x, y, map, valueMap, new Set()));
    }
    return res;
};
function dfs(x, y, map, valueMap, set) {
    if(x === y) return 1.0;
    set.add(x);
    let nextList = map.get(x);
    let valueList = valueMap.get(x);
    for(let i = 0; i < nextList.length; i++) {
        if(set.has(nextList[i])) continue;
        let t = dfs(nextList[i], y, map, valueMap, set);
        if(t > -1.0) return valueList[i] * t;
    }
    return -1.0;
}

C++(DFS)

public:
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        unordered_map<string, unordered_map<string, double>> map;
        for(int i = 0; i < equations.size(); i++) {
            const string& x = equations[i].first;
            const string& y = equations[i].second;
            const double v = values[i];
            map[x][y] = v;
            map[y][x] = 1.0 / v;
        }
        vector<double> res;
        for(const auto& pair : queries) {
            const string& x = pair.first;
            const string& y = pair.second;
            if(!map.count(x) || !map.count(y)) {
                res.push_back(-1.0);
                continue;
            }else {
                unordered_set<string> set;
                res.push_back(dfs(x, y, map, set));
            }
        }
        return res;
    }
private:
    double dfs(const string& x, const string& y, unordered_map<string, unordered_map<string, double>> map, unordered_set<string> set) {
        if(x == y) return 1.0;
        set.insert(x);
        for(const auto& pair : map[x]) {
            const string& next = pair.first;
            if(set.count(next)) continue;
            double t = dfs(next, y, map, set);
            if(t > -1.0) return map[x][next] * t;
        }
        return -1.0;
    }

C++(Union Find)

public:
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        unordered_map<string, pair<string, double>> parents;
        for(int i = 0; i < equations.size(); i++) {
            const string& x = equations[i].first;
            const string& y = equations[i].second;
            const double v = values[i];
            if(!parents.count(x) && !parents.count(y)) {
                parents[x] = {y, v};
                parents[y] = {y, 1.0};
            }else if(!parents.count(y)) {
                parents[y] = {x, 1.0 / v};
            }else if(!parents.count(x)) {
                parents[x] = {y, v};
            }else{
                const auto& root_x = find(x, parents);
                const auto& root_y = find(y, parents);
                parents[root_x.first] = {root_y.first, v / root_x.second * root_y.second};
            }
        }

        vector<double> res;
        for(const auto& pair : queries) {
            const string& x = pair.first;
            const string& y = pair.second;
            if(!parents.count(x) || !parents.count(y)) {
                res.push_back(-1.0);
                continue;
            }
            auto& root_x = find(x, parents);
            auto& root_y = find(y, parents);
            if(root_x.first != root_y.first) {
                res.push_back(-1.0);
            }else{
                res.push_back(root_x.second / root_y.second);
            }
        }
        return res;
    }
private:
    pair<string, double>& find(const string& n, unordered_map<string, pair<string, double>>& parents) {
        if(n != parents[n].first) {
            const auto& p = find(parents[n].first, parents);
            parents[n].first = p.first;
            parents[n].second *= p.second;
        }
        return parents[n];
    }