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

Hint

Train of Thought

The logic I have used is to construct a Map of maps, that contains all possible a/b and b/a from the given input and their values.

For the given input equations = [ ["a", "b"], ["b", "c"] ]. values = [2.0, 3.0]

The map that gets constructed is :

[a: [b:2.0] b: [a:0.5], [c:3.0] c: [b:0.333]]

For each key in the outer map, the value represents a map, that denotes all possible denominators for the key and the corresponding key/value.

With this map constructed, the logic for evaluating a query is simple in a dfs style:

To find any m/n, if the map of m contains x1, x2, x3 then m/n = m/x1 x1/n if this gives a valid result or m/x2 x2/n or m/x3 * x3/n

Code

//Similar idea here with hashmap inside a hashmap.
 public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
    HashMap<String, HashMap<String, Double>> map = new HashMap<String, HashMap<String, Double>>();
    for (int i = 0; i < equations.length; ++i) {
        if (!map.containsKey(equations[i][0]))
            map.put(equations[i][0], new HashMap<String, Double>());
        if (!map.containsKey(equations[i][1]))
            map.put(equations[i][1], new HashMap<String, Double>());
        map.get(equations[i][0]).put(equations[i][1], values[i]);
        map.get(equations[i][1]).put(equations[i][0], 1 / values[i]);
    }
    double[] out = new double[queries.length];
    for (int i = 0; i < queries.length; ++i) {
        if (map.containsKey(queries[i][0]) && map.containsKey(queries[i][1])) {
            if (queries[i][0] == queries[i][1])
                out[i] = 1.0;
            else {
                double judg = dfs(queries[i][0], queries[i][1], new HashSet<String>(), map, 1.0);
                out[i] = judg == 0.0 ? -1.0 : judg;
            }
        }
        else out[i] = -1.0;
    }
    return out;
}

private double dfs(String s, String t, HashSet<String> visited, HashMap<String, HashMap<String, Double>> map, double val) {
    if (map.get(s).containsKey(t)) 
        return val * map.get(s).get(t);
    double tmp = 0.0;
    for (String neighbor : map.get(s).keySet()) {
        if (!visited.contains(neighbor)) {
            visited.add(neighbor);
            tmp = dfs(neighbor, t, visited, map, val * map.get(s).get(neighbor));
            if (tmp != 0.0) break;
        }
    }
    return tmp;
}


//another idea using floyd-warshall like algorithm
public double[] calcEquation(String[][] equations, double[] values, String[][] query) {
        // use table save string to integer
        Map<String, Integer> table = new HashMap<>();
        int len = 0;
        for (String[] strings : equations)
            for (String string : strings)
                if (!table.containsKey(string)) table.put(string, len++);

        // init map by direct equation
        double[][] map = new double[len][len];
        for (int i = 0; i < len; ++i)
            for (int j = 0; j < len; ++j)
                map[i][j] = (i == j ? 1.0d : -1.0d);
        for (int i = 0; i < equations.length; ++i) {
            String[] keys = equations[i];
            int row = table.get(keys[0]);
            int col = table.get(keys[1]);
            map[row][col] = values[i];
            map[col][row] = 1 / values[i];
        }

        // floyd-warshall like algorithm
        for (int i = 0; i < len; ++i) {
            for (int j = 0; j < len; ++j) {
                for (int k = 0; k < len; ++k) {
                    if (map[j][i] >= 0d && map[i][k] >= 0d) map[j][k] = map[j][i] * map[i][k];
                }
            }
        }

        // query now
        double[] result = new double[query.length];
        for (int i = 0; i < query.length; ++i) {
            String[] keys = query[i];
            Integer row = table.get(keys[0]);
            Integer col = table.get(keys[1]);
            if (row == null || col == null) result[i] = -1.0d;
            else result[i] = map[row][col];
        }
        return result;
    }

Complexity