Java 2 ms solution, graph dfs + map

• ``````public class Solution {
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
Map<String, Integer> map = new HashMap<>();
buildMap(equations, map);
final int N = map.size();
double[][] graph = new double[N][N];
buildGraph(graph, equations, values, map);
double[] ans = new double[queries.length];
int index = 0, x=-1, y=-1;
for(String[] query : queries){
x = map.getOrDefault(query[0], -1);
y = map.getOrDefault(query[1], -1);
if(x<0||y<0)
ans[index] = -1.0;
else if(x==y)
ans[index] = 1.0;
else if (graph[x][y]!=0)
ans[index] = graph[x][y];
else{
graph[x][y] = calLength(1.0, x, y, graph, new boolean[N][N]);
ans[index] = graph[x][y];
graph[y][x] = 1.0/graph[x][y];
}
index++;
}
return ans;
}
private void buildMap(String[][] equations, Map<String, Integer> map){
int index = 0;
for(String[] equation : equations){
for(String node : equation){
if(!map.containsKey(node)) {
map.put(node, index);
index++;
}
}
}
}
private void buildGraph(double[][] graph, String[][] equations, double[] values, Map<String, Integer> map){
int x=0, y=0, i=0;
for(String[] equation : equations){
x = map.get(equation[0]);
y = map.get(equation[1]);
graph[x][y] = values[i];
graph[y][x] = 1.0/values[i];
i++;
}
}
private double calLength(double curL, int x, int y, double[][] graph, boolean[][] visit){
if(x==y || graph[x][y]>0) return graph[x][y]*curL;
double len = -1;
for(int i=0; i<graph.length; i++){
if(graph[x][i]>0 && !visit[x][i]){
visit[x][i] = true;
len = calLength(graph[x][i]*curL, i, y, graph, visit);
if(len>0) break;
}
}
return len;
}

}
``````

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