# Share my Java DFS solution

• Basic idea is pretty simple: construct graph and do DFS for each query. The optimization is as long as we find a answer, we can directly jump out from recursion instead of go through all rest of relations since there is no contradiction.

``````public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
double[] result = new double[queries.length];

HashMap<String, HashMap<String, Double>> mapping = new HashMap<String, HashMap<String, Double>>();

// Construct graph
for (int i = 0; i < equations.length; i++){
String key = equations[i][0];
String val = equations[i][1];
double ratio = values[i];
if (!mapping.containsKey(key)){
HashMap<String, Double> hm1 = new HashMap<String, Double>();
mapping.put(key, hm1);
}
if (!mapping.containsKey(val)){
HashMap<String, Double> hm2 = new HashMap<String, Double>();
mapping.put(val, hm2);
}
mapping.get(key).put(val, ratio);
mapping.get(val).put(key, 1.0/ratio);
}
int idx = 0;

for (int i = 0; i < queries. length; i++){
String start = queries[i][0];
String end = queries[i][1];
if (mapping.containsKey(start) && mapping.containsKey(end)){
boolean[] flag = new boolean[1]; // As long as we find one solution,
//we can end the recursion of current query
dfs(start, end, "", mapping, result, idx, 1, flag);
if(flag[0]){
idx++;
}else{
result[idx++] = -1.0;
}
}else{
result[idx++] = -1.0;
}
}

return result;
}

public void dfs(String start, String end, String pre, HashMap<String, HashMap<String, Double>> mapping, double[] result, int idx, double total, boolean[] flag){
HashMap<String, Double> hm = mapping.get(start);
if (hm.size() == 0 && !start.equals(end)){
return;
}

if (start.equals(end)){
result[idx] = total;
flag[0] = true;
return;
}
Iterator it = hm.entrySet().iterator();
while (it.hasNext()){
Map.Entry pair = (Map.Entry) it.next();
String nextString = (String)pair.getKey();

// ignore previous node
if (!nextString.equals(pre)){
Double value = (Double)pair.getValue();
dfs(nextString, end, start, mapping, result, idx, total * value, flag);
if (flag[0]){
return;
}
}
}
}
``````

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