Java Graph based solution. No DFS is needed. 3ms


  • 5
    T

    I have calculated all the possible distances between graph nodes during the construction of the graph. DFS need not be used as all the possible distances between nodes are already calculated in the adjacency matrix exhaustively.

    public class Solution {
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            
            
            HashMap<String, Integer> nodes = new HashMap<String, Integer>();
            int nodeCount = 0;
            for(String[] eq : equations) {
                
                String src = eq[0];
                String dest = eq[1];
                
                if(!nodes.containsKey(src)) {
                    nodes.put(src, nodeCount++);
                }
                if(!nodes.containsKey(dest)) {
                    nodes.put(dest, nodeCount++);
                }
            }
            
            double[][] map = new double[nodeCount][nodeCount];
            int len = equations.length;
            if(values.length != len) return null;
            
            for(int i = 0; i < len; i++) {
                String[] eq = equations[i];
                double val = values[i];
                int src = nodes.get(eq[0]);
                int dest = nodes.get(eq[1]);
                
                map[src][dest] = val;
                map[src][src] = 1.0;
                map[dest][dest] = 1.0;
                map[dest][src] = 1.0 / val;
            }
            
            for(int i = 0 ; i < nodeCount; i++) {
                for(int j = 0 ; j < nodeCount; j++) {
                    for(int k = 0 ; k < nodeCount; k++) {
                        if(map[i][j] == 0 || map[j][k] == 0) continue;
                        map[i][k] = map[i][j] * map[j][k];     
                    }
                }
            }
            
            double res[] = new double[queries.length];
            len = queries.length;
            for(int i = 0; i < len; i++) {
                String[] eq = queries[i];
                Integer src = nodes.get(eq[0]);
                Integer dest = nodes.get(eq[1]);
                if(src == null || dest == null ){
                    res[i] = -1.0;
                    continue;
                }
                double val = map[src][dest];
                if(val == 0) res[i] = -1.0;
                else res[i] = val;
            }
            return res;
        }
    }
    

  • 0
    This post is deleted!

Log in to reply
 

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