My Java DFS+hashmap solution


  • 0
    W

    See explanation in comments.

    class Solution {
        HashMap<Pair, Double> ratios;
        HashMap<String, List<Pair>> varToPairs;
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            ratios = new HashMap<>();
            varToPairs = new HashMap<>();
            
            // Step 1. figure out all the possible ratios, and the list of pairs for each variable
            // for the given input, we would get
            //     ratios: (a,b)->2, (b,a)->0.5, (b,c)->3, (c,b)->1/3
            //     varToPairs: a->[(a,b)]
            //                 b->[(b,a), (b,c)]
            //                 c->[(c,b)]
            for (int i = 0; i < equations.length; i ++) {
                String[] e = equations[i];
                double ratio = values[i];
                
                Pair pair = new Pair(e[0], e[1]);
                Pair reversePair = new Pair(e[1], e[0]);
                
                ratios.put(pair, ratio);
                ratios.put(reversePair, 1 / ratio);
    
                List<Pair> pairsForFirst = varToPairs.getOrDefault(e[0], new ArrayList<Pair>());
                pairsForFirst.add(pair);
                varToPairs.put(e[0], pairsForFirst);
    
                List<Pair> pairsForSecond = varToPairs.getOrDefault(e[1], new ArrayList<Pair>());
                pairsForSecond.add(reversePair);
                varToPairs.put(e[1], pairsForSecond);
            }
            
            
            // Step 2. for each query, traverse the graph
            double[] ans = new double[queries.length];
            int i = 0;
            for (String[] q : queries) {            
                Double v = dfs(new Pair(q[0], q[1]), new HashSet<Pair>());
                ans[i++] = (v == null) ? -1 : v;            
            }
            
            return ans;
        }
        
        Double dfs(Pair query, HashSet<Pair> visited) {
            if (!varToPairs.containsKey(query.first)) return null;
            
            List<Pair> pairs = varToPairs.get(query.first);
            for (Pair pair : pairs) {
                if (visited.contains(pair)) continue;
                visited.add(pair);
                
                double r = ratios.get(pair);
                
                if (query.equals(pair)) {
                    // found the answer
                    return r;
                } else {
                    Pair newPair = new Pair(pair.second, query.second);
                    Double subAns = dfs(newPair, visited);
                    if (subAns != null) return r * subAns;
                }
            }
            
            return null;
        }
        
        class Pair {
            String first;
            String second;
            public Pair(String s1, String s2) {
                first = s1;
                second = s2;
            }
            @Override
            public boolean equals(Object obj) {
                if (obj.getClass() != getClass()) return false;
                
                Pair p = (Pair)obj;
                return first.equals(p.first) && second.equals(p.second);
            }
            
            @Override
            public int hashCode() {
                return first.hashCode() * 31 + second.hashCode();
            }
            
            @Override
            public String toString() {
                return "(" + first + ", " + second + ")";
            }
        }
        
    }
    

Log in to reply
 

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