Java graph solution 4ms using matrix


  • 0
    Q

    The solution is to use a matrix to represent the graph. look for a path which can get the result
    for example, given [[a,b], [a,c]] the way to get bc is b->a->c
    and cache the traversed path if it's already calculated

    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        int index = 0;
        Map<String, Integer> map = new HashMap();
        // max size is values.lengt*2
        // init the graph and fill in values
        double[][] graph = new double[values.length * 2][values.length * 2];
        for(int i = 0; i < equations.length; i++){
            String[] ops = equations[i];
            if(!map.containsKey(ops[0])){
                map.put(ops[0],index);
                index++;
            }
            if(!map.containsKey(ops[1])){
                map.put(ops[1],index);
                index++;
            }
            graph[map.get(ops[0])][map.get(ops[1])] = values[i];
            graph[map.get(ops[1])][map.get(ops[0])] = 1/values[i];
        }
    
        double[] rt = new double[queries.length];
        for(int i = 0 ; i < queries.length; i++){
            String a = queries[i][0];
            String b = queries[i][1];
            Integer op1 = map.get(a);
            Integer op2 = map.get(b);
            // if operand doesn't exist
            if(op1 == null || op2 == null) {
                rt[i] = -1;
                continue;
            }
            // if two operands are the same
            if(op1 == op2) {
                rt[i] = 1;
                continue;
            }
            List<Double> path = new ArrayList();
            
            findPath(graph, path, op1, op2, -1);
            if(path.size() == 0){
                rt[i] = -1;
                continue;
            }
            double curR = 1;
            for(Double r : path){
                curR *= r;
            }
            rt[i] = curR;
        }
        return rt;
    }
    
    boolean findPath(double[][] graph, List<Double> path, int op1, int op2, int parent){
        if(graph[op1][op2] != 0){
            path.add(graph[op1][op2]);
            return true;
        }
    
        for(int i =0; i < graph.length; i++){
            if(graph[op1][i] != 0 && i != parent){
                path.add(graph[op1][i]);
                boolean found = findPath(graph, path, i, op2, op1);
                if(found){
                    // memorize 
                    double curR = 1;
                    for(Double r : path){
                        curR *= r;
                    }
                    graph[op1][op2] = curR;
                    return true;
                }
                path.remove(path.size() - 1);
            }
        }
        return false;
    }
    

Log in to reply
 

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