Easy to understand JAVA solution (DFS)


  • 0
    P

    Easy to understand solution using DFS with Map and Set

    class Solution {
        Map<String, Map<String, Double>> equationMap = new HashMap<>();
        Map<String, Set<String>> visitedMap;
        
        Double NOT_FOUND = -1.00;
        
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            for(int i=0;i<equations.length;i++){
                String[] equation = equations[i];
                putAB(equation[0], equation[1], values[i]);
                // set the edge with reverse division as well
                putAB(equation[1], equation[0], 1/values[i]);
            }
        
            System.out.println(equationMap);
            double [] resultArray = new double[queries.length];
            
            int i=0;
            for(String[] query: queries){
                visitedMap = new HashMap<>();
                System.out.println(query[0]+"::" + query[1]);
                resultArray[i] = evaluatePath(query[0], query[1]);
                i++;
            }
            
            return resultArray;
        }
        
        public Double evaluatePath(String u, String t){
            System.out.println(u+":" + t);
            if(hasAB(u,t)){
                return getAB(u,t);
            } else {
                Map<String, Double> valueMap = equationMap.get(u) != null? equationMap.get(u) : new HashMap<>();
                for(String s: valueMap.keySet()){
                    if(!isABVisited(u,s)){
                        setABVisited(u,s);
                        Double ret = evaluatePath(s,t);
                        if(ret != NOT_FOUND){
                            ret = ret * getAB(u,s);
                            return ret;
                        }
                    }        
                }
            }
            return NOT_FOUND;
        }
        
        private double getAB(String a, String b){
            return equationMap.get(a).get(b);
        }
        
        private boolean hasAB(String a, String b){
            return equationMap.containsKey(a) ? equationMap.get(a).containsKey(b) : false;
        }
        
        private void putAB(String a, String b, double val){
                Map<String, Double> valueMap = equationMap.get(a);
                if(valueMap == null){
                    valueMap = new HashMap<>();
                    equationMap.put(a, valueMap);
                }
                valueMap.put(b, val);
        }
        
        private boolean isABVisited(String a, String b){
            return visitedMap.containsKey(a) ? visitedMap.get(a).contains(b):false;
        }
        
        private void setABVisited(String a, String b){
            Set<String> visitedSet = visitedMap.get(a);
                if(visitedSet == null){
                    visitedSet = new HashSet<>();
                    visitedMap.put(a, visitedSet);
                }
                visitedSet.add(b);
        }
    }
    

Log in to reply
 

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