# Java 3ms Solution (Graph Traverse & Index Map)

• ``````class Solution {
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
int m = values.length, n = queries.length;
double[] ret = new double[n];

//match String with Index
Map<String, Integer> idx = new HashMap<String, Integer>();
int index = 0;
for(int i = 0; i < m; i++){
if(idx.get(equations[i][0]) == null) idx.put(equations[i][0], index++);
if(idx.get(equations[i][1]) == null) idx.put(equations[i][1], index++);
}

//init Graph
double[][] graph = new double[index][index];
for(int i = 0; i < index; i++){
for(int j = 0; j < index; j++){
graph[i][j] = -1.0;
}
}
for(int i = 0; i < m; i++){
if(equations[i][0].equals(equations[i][1])) continue;
graph[idx.get(equations[i][0])][idx.get(equations[i][1])] = values[i];
if(values[i] != 0) graph[idx.get(equations[i][1])][idx.get(equations[i][0])] = 1.0 / values[i];
}
//traverse graph
for(int i = 0; i < index; i++){
for(int j = 0; j < index; j++){
if(i == j || graph[i][j] != -1.0 || graph[j][i] == 0.0) continue;
for(int k = 0; k < index; k++){
if(k == i || k == j || graph[i][k] == -1.0 || graph[k][j] == -1.0 || graph[k][j] == 0.0) continue;
graph[i][j] = graph[i][k] * graph[k][j];
}
}
}

//returns of queries
for(int i = 0; i < n; i++){
if(idx.get(queries[i][0]) == null || idx.get(queries[i][1]) == null) ret[i] = -1.0;
else if(queries[i][0].equals(queries[i][1])) ret[i] = 1.0;
else ret[i] = graph[idx.get(queries[i][0])][idx.get(queries[i][1])];
}
return ret;
}
}
``````

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