# My Java DFS+hashmap solution

• See explanation in comments.

``````class Solution {
HashMap<Pair, Double> ratios;
HashMap<String, List<Pair>> varToPairs;
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
ratios = new HashMap<>();
varToPairs = new HashMap<>();

// Step 1. figure out all the possible ratios, and the list of pairs for each variable
// for the given input, we would get
//     ratios: (a,b)->2, (b,a)->0.5, (b,c)->3, (c,b)->1/3
//     varToPairs: a->[(a,b)]
//                 b->[(b,a), (b,c)]
//                 c->[(c,b)]
for (int i = 0; i < equations.length; i ++) {
String[] e = equations[i];
double ratio = values[i];

Pair pair = new Pair(e[0], e[1]);
Pair reversePair = new Pair(e[1], e[0]);

ratios.put(pair, ratio);
ratios.put(reversePair, 1 / ratio);

List<Pair> pairsForFirst = varToPairs.getOrDefault(e[0], new ArrayList<Pair>());
varToPairs.put(e[0], pairsForFirst);

List<Pair> pairsForSecond = varToPairs.getOrDefault(e[1], new ArrayList<Pair>());
varToPairs.put(e[1], pairsForSecond);
}

// Step 2. for each query, traverse the graph
double[] ans = new double[queries.length];
int i = 0;
for (String[] q : queries) {
Double v = dfs(new Pair(q[0], q[1]), new HashSet<Pair>());
ans[i++] = (v == null) ? -1 : v;
}

return ans;
}

Double dfs(Pair query, HashSet<Pair> visited) {
if (!varToPairs.containsKey(query.first)) return null;

List<Pair> pairs = varToPairs.get(query.first);
for (Pair pair : pairs) {
if (visited.contains(pair)) continue;

double r = ratios.get(pair);

if (query.equals(pair)) {
// found the answer
return r;
} else {
Pair newPair = new Pair(pair.second, query.second);
Double subAns = dfs(newPair, visited);
if (subAns != null) return r * subAns;
}
}

return null;
}

class Pair {
String first;
String second;
public Pair(String s1, String s2) {
first = s1;
second = s2;
}
@Override
public boolean equals(Object obj) {
if (obj.getClass() != getClass()) return false;

Pair p = (Pair)obj;
return first.equals(p.first) && second.equals(p.second);
}

@Override
public int hashCode() {
return first.hashCode() * 31 + second.hashCode();
}

@Override
public String toString() {
return "(" + first + ", " + second + ")";
}
}

}
``````

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