Java Solution: verbose but hopefully easy to understand


  • 0
    A
    public class Solution {
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            // algorithm 2017/06/15: it is really a directed graph problem, that we have N nodes and M edges connecting from one node pointing to another. Given a pair of node (a,b), find the route
            // use DFS
            HashMap<String, List<Equation>> equationObjects = new HashMap<>();
            buildEquations(equations, values, equationObjects);
    
            double[] results = new double[queries.length];
            for (int index = 0; index < queries.length; index++) {
                results[index] = evaluate(queries[index], equationObjects);
            }
            return results;
        }
    
        private void buildEquations(String[][] equations, double[] values, HashMap<String, List<Equation>> equationObjects) {
            for (int index = 0; index < equations.length; index++) {
                String top = equations[index][0];
                String down = equations[index][1];
                double value = values[index];
    
                {
                    List<Equation> topAsEnumerators = equationObjects.get(top);
                    if (null == topAsEnumerators) {
                        topAsEnumerators = new ArrayList<>();
                        equationObjects.put(top, topAsEnumerators);
                    }
                    topAsEnumerators.add(new Equation(top, down, value));
                }
    
                // add a peer expression
                if (!down.equals(top)) {
                    List<Equation> downAsEnumerators = equationObjects.get(down);
                    if (null == downAsEnumerators) {
                        downAsEnumerators = new ArrayList<>();
                        equationObjects.put(down, downAsEnumerators);
                    }
                    downAsEnumerators.add(new Equation(down, top, 1.0 / value));
                }
            }
        }
    
        private double evaluate(String[] query, HashMap<String, List<Equation>> equationObjects) {
            assert null != equationObjects;
            String top = query[0];
            String down = query[1];
    
            // search the graph: a/f ==> a/b * b/e * e/g * g/f
            double result = 1.0;
            Set<String> visited = new HashSet<>();
            return evaluate(top, down, result, equationObjects, visited);
        }
    
        private double evaluate(String top, String down, double result, HashMap<String, List<Equation>> equationObjects, Set<String> visited) {
            // recursion
            List<Equation> topAsEnumerators = equationObjects.get(top);
            if (null == topAsEnumerators) {
                return -1.0;
            }
            // both are the same
            if (top.equals(down)) {
                return result * 1.0;
            }
            // DFS
            visited.add(top);
            for (Equation expression : topAsEnumerators) {
                if (expression.down.equals(down)) {
                    return result * expression.value;
                } else {
                    // use expression.down as the new top, but do not do if expression.down==top, otherwise infinite loop
                    if (visited.contains(expression.down)) {
                        continue;       // skip
                    }
                    double tryIt = evaluate(expression.down, down, result * expression.value, equationObjects, visited);
                    if (tryIt > 0) {
                        return tryIt;
                    }
                }
            }
            return -1.0;
        }
    
        class Equation {
            public Equation(String top, String down, double value) {
                this.top = top;
                this.down = down;
                this.value = value;
            }
    
            String top, down;
            double value;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.