# Java Solution: verbose but hopefully easy to understand

• ``````public class Solution {
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
// algorithm 2017/06/15: it is really a directed graph problem, that we have N nodes and M edges connecting from one node pointing to another. Given a pair of node (a,b), find the route
// use DFS
HashMap<String, List<Equation>> equationObjects = new HashMap<>();
buildEquations(equations, values, equationObjects);

double[] results = new double[queries.length];
for (int index = 0; index < queries.length; index++) {
results[index] = evaluate(queries[index], equationObjects);
}
return results;
}

private void buildEquations(String[][] equations, double[] values, HashMap<String, List<Equation>> equationObjects) {
for (int index = 0; index < equations.length; index++) {
String top = equations[index][0];
String down = equations[index][1];
double value = values[index];

{
List<Equation> topAsEnumerators = equationObjects.get(top);
if (null == topAsEnumerators) {
topAsEnumerators = new ArrayList<>();
equationObjects.put(top, topAsEnumerators);
}
}

if (!down.equals(top)) {
List<Equation> downAsEnumerators = equationObjects.get(down);
if (null == downAsEnumerators) {
downAsEnumerators = new ArrayList<>();
equationObjects.put(down, downAsEnumerators);
}
downAsEnumerators.add(new Equation(down, top, 1.0 / value));
}
}
}

private double evaluate(String[] query, HashMap<String, List<Equation>> equationObjects) {
assert null != equationObjects;
String top = query[0];
String down = query[1];

// search the graph: a/f ==> a/b * b/e * e/g * g/f
double result = 1.0;
Set<String> visited = new HashSet<>();
return evaluate(top, down, result, equationObjects, visited);
}

private double evaluate(String top, String down, double result, HashMap<String, List<Equation>> equationObjects, Set<String> visited) {
// recursion
List<Equation> topAsEnumerators = equationObjects.get(top);
if (null == topAsEnumerators) {
return -1.0;
}
// both are the same
if (top.equals(down)) {
return result * 1.0;
}
// DFS
for (Equation expression : topAsEnumerators) {
if (expression.down.equals(down)) {
return result * expression.value;
} else {
// use expression.down as the new top, but do not do if expression.down==top, otherwise infinite loop
if (visited.contains(expression.down)) {
continue;       // skip
}
double tryIt = evaluate(expression.down, down, result * expression.value, equationObjects, visited);
if (tryIt > 0) {
return tryIt;
}
}
}
return -1.0;
}

class Equation {
public Equation(String top, String down, double value) {
this.top = top;
this.down = down;
this.value = value;
}

String top, down;
double value;
}
}``````

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