Easy to Understand Solution Using Map and DFS


  • 0
    K
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        //build a map to track a string and all other strings that can be computed from it
        //use dfs to calculate a query
        Map<String, Map<String, Double>> map = new HashMap<String, Map<String, Double>>();
        for (int i = 0; i < equations.length; i++) {
            String numerator = equations[i][0];
            String denorminator = equations[i][1];
            Double f = values[i];
            if (!map.containsKey(numerator)) {
                map.put(numerator, new HashMap<String, Double>());
            }
            if (!map.containsKey(denorminator)) {
                map.put(denorminator, new HashMap<String, Double>());
            }
            map.get(numerator).put(denorminator, f);
            map.get(denorminator).put(numerator, 1 / f);
        }
        int len = queries.length;
        double[] result = new double[len];
        for (int i = 0; i < len; i++) {
            String numerator = queries[i][0];
            String denorminator = queries[i][1];
            Set<String> his = new HashSet<String>();
            result[i] = calculate(numerator, denorminator, map, 1.0, his);
        }
        return result;
    }
    
    private double calculate(String numerator, String denorminator, Map<String, Map<String, Double>> map, double f, Set<String> his) {
        double noResult = -1.0;
        if (!map.containsKey(numerator) || !map.containsKey(denorminator) || his.contains(numerator)) {
            return noResult;
        }
        if (numerator.equals(denorminator))
            return f;
        if (map.get(numerator).containsKey(denorminator)) {
            return f * map.get(numerator).get(denorminator);
        }
        his.add(numerator);
        for (String nextNumerator : map.get(numerator).keySet()) {
            double nextResult = calculate(nextNumerator, denorminator, map, f*map.get(numerator).get(nextNumerator), his);
            if (nextResult != -1.0)
                return nextResult;
        }
        return noResult;
    }

Log in to reply
 

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