Java 2 ms solution, graph dfs + map


  • 2
    M
    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;
        }
        
    }
    

Log in to reply
 

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