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; } }