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.

答案

class Solution {

    /*
        思路

        Model each letter as a node, the relationship between two letters as an edge
        Given the example above, we have the following graph:
        a---2-->b
        b---1/2-->a
        b---3-->c
        c---1/3-->b
    */

    class GEdge {
        double weight;
        String dest;

        public GEdge(double weight, String dest) {
            this.weight = weight;
            this.dest = dest;
        }
    }

    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        Map<String,List<GEdge>> g = new HashMap<>();

        // Build graph here
        for(int i = 0; i < equations.length; i++) {
            String numerator = equations[i][0];
            String denominator = equations[i][1];

            // Add this edge to node numerator
            List<GEdge> edges = g.get(numerator);
            if(edges == null) {
                edges = new ArrayList<GEdge>();
                g.put(numerator, edges);
            }
            edges.add(new GEdge(values[i], denominator));

            // Add this edge to node denominator
            edges = g.get(denominator);
            if(edges == null) {
                edges = new ArrayList<GEdge>();
                g.put(denominator, edges);
            }
            edges.add(new GEdge(1 / values[i], numerator));
        }
        // Dfs search here
        double[] ans = new double[queries.length];
        Set<String> visited = new HashSet<>();
        for(int i = 0; i < queries.length; i++) {
            if(!g.containsKey(queries[i][0]) || !g.containsKey(queries[i][1]))
                ans[i] = -1.0;
            else
                ans[i] = dfs(g, visited, queries[i][0], queries[i][1], 1.0);
        }
        return ans;
    }

    /*
        Start from numerator, search for denominator
        If not found return -1.0
        Otherwise return the edge weight from parent node to current node

    */
    public double dfs(Map<String,List<GEdge>> g, Set<String> visited, String curr, String denominator, double edge_weight) {
        if(curr.equals(denominator)) {
            return edge_weight;
        }

        double ret = -1.0;
        visited.add(curr);
        List<GEdge> edges = g.get(curr);
        for(GEdge e : edges) {
            if(!visited.contains(e.dest)) {
                ret = dfs(g, visited, e.dest, denominator, e.weight);
                if(ret != -1.0) break;
            }
        }
        visited.remove(curr);
        if(ret == -1.0) return ret;
        return ret * edge_weight;
    }
}