# My java solution use Map and dfs with explanation

• Let's use default example:

``````equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
``````

[1] setup map (key is current string, value is a set)
the set is contain an entry (key is relate string, value is relate value)

``````  for example :

equations[0][0] : "a" is current string , "b" is relate string, value is "a"/"b"=2.0;
so, In the map: "a" --> Set { ("b" --> 1.0) };

equations[0][1] : "b" is current string , "a" is relate string, value is "b"/"a"=0.5;
so, In the map: "b" --> Set { ("a" --> 0.5) };

equations[1][0] : "b" is current string , "c" is relate string, value is "b"/"c"=3.0;
so, In the map: "b" --> Set { ("a" --> 0.5) , ("c" --> 3.0)};
``````

[2] setup mark (default is false)

[3] use depth first search to search the graph

`````` when we visit one string, mark that string, which indicates this string will not visit again

for example:

res[0] = "a" -> ("b", 2.0) -> ("c", 3.0) = 2.0*3.0
``````
``````import java.util.*;
import java.util.Map.Entry;
public class Solution {
double[] res;
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
Map<String, Set<Entry<String, Double>>> map = new HashMap<>();
Map<String, Boolean> mark = new HashMap<String, Boolean>();

for (int i = 0; i < equations.length; i++) {
for (int j = 0; j < 2; j++) {
Set<Entry<String, Double>> list = map.getOrDefault(equations[i][j], new HashSet<>());
list.add(new AbstractMap.SimpleEntry<String, Double>(equations[i][~j&1], j==0? values[i] : 1/values[i]));
map.put(equations[i][j], list);
mark.put(equations[i][j], false);
}
}

res = new double[queries.length];
for (int i = 0; i < queries.length; i++) {
res[i] = -1.0;
if (map.containsKey(queries[i][0]) && map.containsKey(queries[i][1])){
helper(i, queries[i][0], queries[i][1], 1.0, map, mark);
for (Entry<String, Boolean> e : mark.entrySet()) mark.put(e.getKey(), false);
}
}
return res;
}

private void helper(int i, String a, String b, double curValue, Map<String, Set<Entry<String, Double>>> map, Map<String, Boolean> mark) {
if (a.equals(b)){res[i] = 1.0;return;}
Set<Entry<String, Double>> set = map.get(a);
mark.put(a, true);
for (Entry<String, Double> entry : set) {
if (!mark.get(entry.getKey()) && res[i] == -1){
if (entry.getKey().equals(b)){
res[i] = curValue*entry.getValue();
return;
}else {
helper(i, entry.getKey(), b, curValue*entry.getValue(), map, mark);
}
}
}
}
}
``````

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