Java 3ms Solution (Graph Traverse & Index Map)


  • 0
    E
    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;
                }
            }
            //load equations and values
            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;
        }
    }
    

Log in to reply
 

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