Java AC solution


  • 0
    C

    The idea is to put all a/b=x relations in a map in the form of "Map<a, Map<b, x>>", and then scan the queries and try to get the values from the map, and store -1 if no values found.

    When we handle each of the equations, we need to scan the map for all the related variables and add all the new relations into the map. This way, when we handle the queries, it's just a simple get() operation, which is O(1) time.

    public class Solution {
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            Map<String, Map<String, Double>> map = new HashMap<>();
            for (int i = 0; i < equations.length; i++) {
                String x = equations[i][0];
                String y = equations[i][1];
                put(values[i], map, x, y);   // put the a/b=x relations in the map
            }
            
            
            double[] res = new double[queries.length];
            for (int i = 0; i < queries.length; i++) {
                if (!map.containsKey(queries[i][0]) || !map.get(queries[i][0]).containsKey(queries[i][1])) {
                    res[i] = -1;
                } else {
                    res[i] = map.get(queries[i][0]).get(queries[i][1]);
                }
            }
            
            return res;
        }
        
        void put(double value, Map<String, Map<String, Double>> map, String x, String y) {
            Map<String, Double> subMap = map.getOrDefault(x, new HashMap<>());
            map.put(x, subMap);
            
            if (!subMap.containsKey(y)) {
                subMap.put(y, value);
            }
            
            // here we need to find all relations between related variables and add them into the map 
            Iterator<String> itr = subMap.keySet().iterator();
            List<Double> puts = new ArrayList<>();
            List<String> xs = new ArrayList<>();
            List<String> ys = new ArrayList<>();
            while (itr.hasNext()) {
                String key = itr.next();
                Double val = subMap.get(key);
                if (!map.containsKey(key) || !map.get(key).containsKey(y)) {
                    puts.add(value / val);
                    xs.add(key);
                    ys.add(y);
                }
            }
            
            for (int i = 0; i < puts.size(); i++) {
                put(puts.get(i) ,map, xs.get(i), ys.get(i));
            }
    
            // handle the y / x = 1/value relation
            subMap = map.getOrDefault(y, new HashMap<>());
            map.put(y, subMap);
            
            if (!subMap.containsKey(x)) {
                subMap.put(x, 1 / value);
            }
    
            itr = subMap.keySet().iterator();
            puts = new ArrayList<>();
            xs = new ArrayList<>();
            ys = new ArrayList<>();
            while (itr.hasNext()) {
                String key = itr.next();
                Double val = subMap.get(key);
                if (!map.get(x).containsKey(key)) {
                    puts.add(value * val);           // notice the difference of the value added
                    xs.add(x);
                    ys.add(key);
                }
            }
            for (int i = 0; i < puts.size(); i++) {
                put(puts.get(i) ,map, xs.get(i), ys.get(i));
            }
        }
    }
    

Log in to reply
 

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