Java super fast solution!!!


  • 0
    K

    class Edge{
    String vertex = "";
    double value = 0.0;
    public Edge(String vertex,double value){
    this.vertex = vertex;
    this.value = value;
    }
    }

    class Result{
    double value = - 1.0;
    }

    public class Solution {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {

        int length = equations.length;
        Map<String,List<Edge>> map = new HashMap<>(); 
        
        //Create a graph with map
        for(int i= 0;i<length;i++){
            List<Edge> list;
            if(map.get(equations[i][0]) != null){
                list = map.get(equations[i][0]);
                Edge edge = new Edge(equations[i][1],values[i]);
                list.add(edge);
            }else{
                list = new ArrayList<>();
                Edge edge = new Edge(equations[i][1],values[i]);
                list.add(edge);
            }
            map.put(equations[i][0],list);
            
            List<Edge> list2;
            if(map.get(equations[i][1]) != null){
                list2 = map.get(equations[i][1]);
                Edge edge = new Edge(equations[i][0],1/values[i]);
                list2.add(edge);
            }else{
                list2 = new ArrayList<>();
                Edge edge = new Edge(equations[i][0],1/values[i]);
                list2.add(edge);
            }
            map.put(equations[i][1],list2);
        }
        
        double[] res = new double[queries.length];
        for(int i=0;i<queries.length;i++){
            if(map.get(queries[i][0]) == null){
                res[i] = -1.0;
                continue;
            }
            
            if(queries[i][0].equals(queries[i][1])){
                res[i] = 1.0;
            }else{
                Set<String> set = new HashSet<>();
                Result result = new Result();
                dfs(map,set,1.0,queries[i][0],queries[i][1],result);
                res[i] = result.value;
            }
        }
        
        return res;
    }
    
    public void dfs(Map<String,List<Edge>> map,Set<String> set,double value,String vertex,String aim,Result result){
        //If already find the value,stop dfs
        if(result.value != -1.0) return;
        
        //Find the aim, save it to result value
        if(vertex.equals(aim)) {
            result.value = value;
            return;
        }
        //If reach a duplicate vertex,stop dfs
        if(set.contains(vertex)) return;
        
        set.add(vertex);
        
        List<Edge> list = map.get(vertex);
        
       //Dfs the graph
        for(int i=0;i<list.size();i++){
            
            dfs(map,set,value*list.get(i).value, list.get(i).vertex ,aim,result);
        }
    }
    

    }


Log in to reply
 

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