Easy AC DFS solution


  • 0
    A
    public class Solution {
         public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
    
            if(equations==null|| values==null || queries ==null || equations.length==0||
                    values.length==0||queries.length==0){
                return new double[0];
    
            }
            int len = queries.length;
            double[] result = new double[len];
            //Create Graph
            HashMap<String,HashMap<String,Double>> graph_map = new HashMap<String, HashMap<String, Double>>();
            int eq_len = values.length;
            for(int i=0;i<eq_len;i++){
                String start = equations[i][0];
                String end = equations[i][1];
                double val = values[i];
                if(!graph_map.containsKey(start)){
                    HashMap<String,Double> map =new HashMap<String, Double>();
                    map.put(end,val);
                    graph_map.put(start,map);
                }else{
                    HashMap<String,Double> map = graph_map.get(start);
                    map.put(end,val);
                    graph_map.put(start,map);
                }
                if(!graph_map.containsKey(end)){
                    HashMap<String,Double> map =new HashMap<String, Double>();
                    map.put(start,1/val);
                    graph_map.put(end,map);
                }else{
                    HashMap<String,Double> map = graph_map.get(end);
                    map.put(start,1/val);
                    graph_map.put(end,map);
                }
    
    
            }
            for(int i=0;i<queries.length;i++){
                String start = queries[i][0];
                String end =queries[i][1];
    
                if(!graph_map.containsKey(start)||!graph_map.containsKey(end)){
                    result[i]=-1.0;
                }else if(start.equals(end)){
                    result[i]=1.0;
                }
                else{
                    double val =DFS(graph_map,1.0,end,start,new HashSet<String>());
                    if(val==0.0){
                        result[i]=-1.0;
                    }
                    else {
                        result[i]=val;
                    }
                }
            }
            
            return result;
    
    
        }
    
        public double DFS(HashMap<String,HashMap<String,Double>> graph, double val, String end, String start, HashSet<String> set){
            HashMap<String ,Double> map = graph.get(start);
            //Set is used to detect cycle
            set.add(start);
            double temp=0.0;
            if(start.equals(end)){
                return 1.0;
            }
    
            if(map.containsKey(end)){
                return val*map.get(end);
            }else{
    
                for(String s: map.keySet()){
                    if(!set.contains(s)){
                    double t = DFS(graph,val*map.get(s),end,s,set);
                    if(t !=0.0){
                        temp=t;
                        break;
                    }
                }
                    
                }
            }
            set.remove(start);
            return temp;
            }
    
    }

Log in to reply
 

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