Evaluate Division

题目地址：
https://leetcode.com/problems/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.

解题思路：
这道题相当于建立一个graph，graph的edge就是两个相邻数字的除的结果。

代码：

public class EvaluateDivision {

    class Vertex{
        String s;
        double times;
        public Vertex(String s){
            this.s = s;
        }
        public void setTimes(double times){
            this.times = times;
        }
    }

    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        if(equations == null || values == null || equations.length == 0 || values.length == 0){
            return new double[0];
        }
        // build the graph by passing two parameters equations and values        Map<String, List<Vertex>> graph = build(equations, values);

        double[] rst = new double[queries.length];
        // method to process queries        for(int i = 0; i <= queries.length - 1; i++){
            rst[i] = processOneQuery(graph, queries[i][0], queries[i][1]);
        }
        return rst;
    }

    private double processOneQuery(Map<String, List<Vertex>> graph, String start, String end) {
        double rst = dfs(graph, new HashSet<String>(), start, end, 1.0);
        return rst;
    }

    private double dfs(Map<String, List<Vertex>> graph, Set<String> visited, String start, String end, double rst) {
        if(start == end && !visited.contains(start) && graph.containsKey(start)){
            return rst;
        }
        if(graph.get(start) == null || visited.contains(start)){
            return -1.0;
        }
        visited.add(start);
        for(Vertex v : graph.get(start)){
            if(visited.contains(v.s)){
                continue;
            }
            double temp = dfs(graph, visited, v.s, end, rst * v.times);
            if(temp != -1.0){
                return temp;
            }
        }
        visited.remove(start);
        return -1.0;
    }

    private Map<String,List<Vertex>> build(String[][] equations, double[] values) {
        Map<String, List<Vertex>> graph = new HashMap<>();
        for(int i = 0; i <= values.length - 1; i++){
            String s1 = equations[i][0];
            String s2 = equations[i][1];
            if(graph.get(s1) == null){
                graph.put(s1, new ArrayList<>());
            }
            Vertex v = new Vertex(s2);
            v.setTimes(values[i]);
            graph.get(s1).add(v);
            // build the reverse            if(graph.get(s2) == null){
                graph.put(s2, new ArrayList<>());
            }
            Vertex v2 = new Vertex(s1);
            v2.setTimes(1 / values[i]);
            graph.get(s2).add(v2);
        }
        return graph;
    }

    public static void main(String[] args){
        EvaluateDivision evaluateDivision = new EvaluateDivision();
        String[][] equations = {{"a", "b"}, {"b", "c"}};
        double[] values = {2.0, 3.0};
        String[][] queries = {{"a", "c"}, {"b", "a"}, {"a", "e"}, {"a", "a"}, {"x", "x"}};
        double[] rst = evaluateDivision.calcEquation(equations, values, queries);
        System.out.println(Arrays.toString(rst));
    }

}

Another version:

public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
    HashMap<String, ArrayList<String>> pairs = new HashMap<String, ArrayList<String>>();
    HashMap<String, ArrayList<Double>> valuesPair = new HashMap<String, ArrayList<Double>>();
    for (int i = 0; i < equations.length; i++) {
        String[] equation = equations[i];
        if (!pairs.containsKey(equation[0])) {
            pairs.put(equation[0], new ArrayList<String>());
            valuesPair.put(equation[0], new ArrayList<Double>());
        }
        if (!pairs.containsKey(equation[1])) {
            pairs.put(equation[1], new ArrayList<String>());
            valuesPair.put(equation[1], new ArrayList<Double>());
        }
        pairs.get(equation[0]).add(equation[1]);
        pairs.get(equation[1]).add(equation[0]);
        valuesPair.get(equation[0]).add(values[i]);
        valuesPair.get(equation[1]).add(1/values[i]);
    }

    double[] result = new double[queries.length];
    for (int i = 0; i < queries.length; i++) {
        String[] query = queries[i];
        result[i] = dfs(query[0], query[1], pairs, valuesPair, new HashSet<String>(), 1.0);
        if (result[i] == 0.0) result[i] = -1.0;
    }
    return result;
}

private double dfs(String start, String end, HashMap<String, ArrayList<String>> pairs, HashMap<String, ArrayList<Double>> values, HashSet<String> set, double value) {
    if (set.contains(start)) return 0.0;
    if (!pairs.containsKey(start)) return 0.0;
    if (start.equals(end)) return value;
    set.add(start);

    ArrayList<String> strList = pairs.get(start);
    ArrayList<Double> valueList = values.get(start);
    double tmp = 0.0;
    for (int i = 0; i < strList.size(); i++) {
        tmp = dfs(strList.get(i), end, pairs, values, set, value*valueList.get(i));
        if (tmp != 0.0) {
            break;
        }
    }
    set.remove(start);
    return tmp;
}