[java/4ms] neat code, DFS, easy to understand

• ``````private double dfs(HashMap<String, HashMap<String, Double>> graph, String start, String end, Set<String> keys) {
// start doesn't exist
HashMap<String, Double> next = graph.get(start);
if (next == null) return -1.0;
// the start node exist
if (start.equals(end)) return 1.0;

double res;
for (Map.Entry<String, Double> entry : next.entrySet()) {
String key = entry.getKey();
res = entry.getValue() * dfs(graph, key, end, keys);
keys.remove(key);
if (res > 0) return res;
}
}

return -1.0;
}

public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
HashMap<String, HashMap<String, Double>> graph = new HashMap<>();
int i = 0;
for (String[] eq : equations) {
// build undirected graph
if (graph.containsKey(eq[0])) {
graph.get(eq[0]).put(eq[1], values[i]);
} else {
HashMap<String, Double> tmp = new HashMap<>();
graph.put(eq[0], tmp);
tmp.put(eq[1], values[i]);
}

if (graph.containsKey(eq[1])) {
graph.get(eq[1]).put(eq[0], 1 / values[i]);
} else {
HashMap<String, Double> tmp = new HashMap<>();
graph.put(eq[1], tmp);
tmp.put(eq[0], 1 / values[i]);
}
i++;
}

double[] res = new double[queries.length];
for (int j = 0; j < queries.length; j++) {
res[j] = dfs(graph, queries[j][0], queries[j][1], new HashSet<>());
}
return res;
}
``````

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