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.

public class Solution {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        Map<String, Map<String, Double>> map = new HashMap<String, Map<String, Double>>();
        for (int i  = 0; i < equations.length; i++) {
            String[] equation = equations[i];
            String a = equation[0];
            String b = equation[1];
            if (!map.containsKey(a)) {
                Map<String, Double> innerMap = new HashMap<String, Double>();
                map.put(a, innerMap);
            }
            map.get(a).put(b, values[i]);
            if (!map.containsKey(b)) {
                Map<String, Double> innerMap = new HashMap<String, Double>();
                map.put(b, innerMap);
            }
            map.get(b).put(a, 1/values[i]);
        }
        double[] results = new double[queries.length];
        for (int i = 0; i < queries.length; i++) {
            String[] query = queries[i];
            results[i] = findValue(map, new HashSet<String>(), query[0], query[1]);
        }
        return results;
    }

    private double findValue(Map<String, Map<String, Double>> map, Set<String> visited, String a, String b) {
        if (!map.containsKey(a) || !map.containsKey(b) || visited.contains(a)) {
            return -1;
        }
        visited.add(a);
        Map<String, Double> innerMap = map.get(a);
        if (innerMap.containsKey(b)) {
            return innerMap.get(b);
        }
        for (Map.Entry<String, Double> entry : innerMap.entrySet()) {
            double valueFound = findValue(map, visited, entry.getKey(), b);
            if (valueFound != -1) {
                return entry.getValue() * valueFound;
            }
        }
        return -1;
    }
}

Leave a comment