Evaluate Division

Weighted Directed Graph -> Find Path Weight

Medium

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 & Analysis

把问题转化为图 Weighted Directed Graph，然后因为不同的路径到达目标path value应该是一样的，因此只需要用DFS找到一个路径即可返回。

建Adjacency List的时候，因为这是带权重的有向图，要顺便添加反向的edge，也就是1.0/value。

Version 2 - DFS

class Solution {
    class Edge {
        String from;
        String to;
        double value;
        Edge(String from, String to, double value) {
            this.from = from;
            this.to = to;
            this.value = value;
        }
    }
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        // Build graph
        HashMap<String, List<Edge>> map = buildGraph(equations, values);
        double[] result = new double[queries.length];

        // Calculate result for each query by searching in the graph
        int idx = 0;
        for (String[] query: queries) {
            if (!map.containsKey(query[0])) {
                result[idx] = -1.0;
            } else {
                String n = query[0];
                String d = query[1];
                HashSet<String> visited = new HashSet < > ();
                double val = dfs(map, visited, 1.0, n, d);
                result[idx] = val;
            }
            idx++;
        }
        return result;
    }

    // Build graph with adjacency list
    private HashMap<String, List<Edge>> buildGraph(String[][] equations, double[] values) {
        HashMap<String, List<Edge>> map = new HashMap<>();
        for (int i = 0; i < equations.length; i++) {
            // convert input equation to edge with value
            if (!map.containsKey(equations[i][0])) {
                map.put(equations[i][0], new ArrayList<Edge>());
            }
            map.get(equations[i][0]).add(new Edge(equations[i][0], equations[i][1], values[i]));
            // reverse order to store inverse value for edge
            if (!map.containsKey(equations[i][1])) {
                map.put(equations[i][1], new ArrayList<Edge>());
            }
            map.get(equations[i][1]).add(new Edge(equations[i][1], equations[i][0], 1.0 / values[i]));
        }
        return map;
    }

    // Recursively search a path from numerator (from) to denominator (to); return -1.0 if not found
    private double dfs(HashMap<String, List<Edge>> map, HashSet<String> visited, double pathVal, String from, String to) {
        if (from.equals(to)) {
            return pathVal;
        }
        visited.add(from);
        List < Edge > edges = map.get(from);
        if (edges != null) {
            for (Edge e: edges) {
                if (visited.contains(e.to)) {
                    continue;
                }
                visited.add(e.to);
                double value = dfs(map, visited, pathVal * e.value, e.to, to);
                if (value != -1.0) {
                    return value;
                }
            }
        }
        return -1.0;
    }
}

Version 1 - DFS (2 ms, faster than 64.65%)

class Solution {
    class Edge {
        String numerator; 
        String denominator;
        double value;
        Edge (String numerator, String denominator, double value) {
            this.numerator = numerator;
            this.denominator = denominator;
            this.value = value;
        }

        // For debugging
        String printString() {
            return numerator + " - " + denominator + ": " + value;
        }
    }
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        // build adjacency list
        HashMap<String, List<Edge>> map = new HashMap<>();
        for (int i = 0; i < equations.length; i++) {
            // convert input equation to edge with value
            if (!map.containsKey(equations[i][0])) {
                map.put(equations[i][0], new ArrayList<Edge>());
            }
            map.get(equations[i][0]).add(new Edge(equations[i][0], equations[i][1], values[i]));

            // reverse order to store inverse value for edge
            if (!map.containsKey(equations[i][1])) {
                map.put(equations[i][1], new ArrayList<Edge>());
            }
            map.get(equations[i][1]).add(new Edge(equations[i][1], equations[i][0], 1.0 / values[i]));
        }

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

        int idx = 0;
        for (String[] query: queries) {
            if (!map.containsKey(query[0])) {
                result[idx] = -1.0;
            } else {
                String n = query[0];
                String d = query[1];
                HashSet<String> visited = new HashSet<>();
                double val = dfs(map, visited, 1.0, n, d);
                result[idx] = val;
            }
            idx++;
        }
        return result;
    }

    private double dfs(HashMap<String, List<Edge>> map, HashSet<String> visited, double val, String numerator, String denominator) {
        if (numerator.equals(denominator)) {
            return val;
        }

        visited.add(numerator);
        List<Edge> edges = map.get(numerator);
        if (edges != null) {
            for (Edge e: edges) {
                if (visited.contains(e.denominator)) {
                    continue;
                }
                visited.add(e.denominator);
                double value = dfs(map, visited, val * e.value, e.denominator, denominator);
                if (value != -1.0) {
                    return value;
                }
            }
        }

        return - 1.0;
    }

    // For debugging
    private void printAdjacencyList (HashMap<String, List<Edge>> map) {

        for (Map.Entry<String, List<Edge>> entry: map.entrySet()) {
            List<Edge> v = entry.getValue();
            for (Edge e: v) {
                System.out.println(e.printString());
            }
        }
    }
}

Reference

https://leetcode.com/problems/evaluate-division/discuss/171649/1ms-DFS-with-Explanations