Easy to understand JAVA solution (DFS)

  • 0

    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]);
            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]);
            return resultArray;
        public Double evaluatePath(String u, String t){
            System.out.println(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()){
                        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);

Log in to reply

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