399. Evaluate Division

Link

Solution

  HashMap<String, String> root = new HashMap<>(); //<node, parent of the node>
    HashMap<String, Double> factor = new HashMap<>(); //<node, node / parent>
    
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        double[] res = new double[queries.size()];
        for(int i = 0; i < values.length; i++){
            List<String> eq = equations.get(i);
            union(eq.get(0), eq.get(1), values[i]);  
        }

        for(int i = 0; i < res.length; i++){
            res[i] = -1;
            List<String> query = queries.get(i);
            String s1 = query.get(0), s2 = query.get(1);
            if(root.containsKey(s1) && root.containsKey(s2) && find(s1).equals(find(s2))){
                res[i] = factor.get(s1)/factor.get(s2);
            }
        }
        return res;
    }
    
    public void union(String source, String base, double value){
        
        root.putIfAbsent(source, source);
        factor.putIfAbsent(source, 1.0);
        root.putIfAbsent(base, base);
        factor.putIfAbsent(base, 1.0);
        
        String srcRoot = find(source);
        String baseRoot = find(base);
        root.put(srcRoot, baseRoot);
        factor.put(srcRoot, factor.get(base)*value/factor.get(source));
        
    }
    
    public String find(String s){
        if(s.equals(root.get(s))) return s;
        
        String parent = root.get(s);
        String ancestor = find(parent);
        root.put(s, ancestor);
        factor.put(s, factor.get(parent)*factor.get(s));
        
        return ancestor;
    }