Java AC solution with explanation


  • 17

    The logic I have used is to construct a Map of maps, that contains all possible a/b and b/a from the given input and their values.

    For the given input
    equations = [ ["a", "b"], ["b", "c"] ]. values = [2.0, 3.0]

    The map that gets constructed is :

    [a: [b:2.0]
    b: [a:0.5], [c:3.0]
    c: [b:0.333]]

    For each key in the outer map, the value represents a map, that denotes all possible denominators for the key and the corresponding key/value.

    With this map constructed, the logic for evaluating a query is simple in a dfs style:

    To find any m/n, if the map of m contains x1, x2, x3
    then
    m/n = m/x1 * x1/n if this gives a valid result or m/x2 * x2/n or m/x3 * x3/n

    public static double[] calcEquation(String[][] equations, double[] values, String[][] query) {
            Map<String, Map<String, Double>> numMap = new HashMap<>();
            int i = 0;
            for(String[] str : equations) {
                insertPairs(numMap, str[0], str[1], values[i]);
                insertPairs(numMap, str[1], str[0], 1.0/values[i]);
                i++;
            }
    
            double[] res = new double[query.length];
            i = 0;
            for(String[] q: query) {
                Double resObj = handleQuery(q[0], q[1], numMap, new HashSet<>());
                res[i++] = (resObj != null) ? resObj : -1.0;
            }
            return res;
        }
    
        public static void insertPairs(Map<String, Map<String, Double>> numMap, String num, String denom, Double value) {
            Map<String, Double> denomMap = numMap.get(num);
            if(denomMap == null) {
                denomMap = new HashMap<>();
                numMap.put(num, denomMap);
            }
            denomMap.put(denom, value);
        }
    
        public static Double handleQuery(String num, String denom, Map<String, Map<String, Double>> numMap, Set<String> visitedSet) {
            String dupeKey = num+":"+denom;
            if(visitedSet.contains(dupeKey)) return null;
            if(!numMap.containsKey(num) || !numMap.containsKey(denom)) return null;
            if(num.equals(denom)) return 1.0;
    
            Map<String, Double> denomMap = numMap.get(num);
            visitedSet.add(dupeKey);
            for(String key : denomMap.keySet()) {
                Double res = handleQuery(key, denom, numMap, visitedSet);
                if(res != null) {
                    return denomMap.get(key) * res;
                }
            }
            visitedSet.remove(dupeKey);
            return null;
        }
    

  • 1
    C

    Good solution.


  • 1
    B

    said in Java AC solution with explanation:
    Any reason to put the add and remove inside the for-loop rather than outside?

    visitedSet.add(dupeKey);
    ...
    visitedSet.remove(dupeKey);

    Thanks.


  • 0

    @bing25 Thanks, they should be outside.


  • 0
    W

    I think it will be efficient to do this before for loop in dfs

    if (numMap.get(num).containsKey(denom)) {
    return numMap.get(num).get(denom);
    }

  • 0
    M

    Two questions:
    Why does visitedSet consist of dupeKeys of the form num:denom? Rather than just num.

    Might be a related question: why do you remove the dupe key after the for loop?

    Thank you!


Log in to reply
 

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