Simple solution using union-find


  • 0
    P

    public class Solution {

    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        int time = 0;
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for (int i = 0; i < values.length; i++) {
            if (!map.containsKey(equations[i][0])) {
                map.put(equations[i][0], time);
                time++;
            }
            if (!map.containsKey(equations[i][1])) {
                map.put(equations[i][1], time);
                time++;
            }
        }
        
        int[] UF = new int[time];
        double[] val = new double[time];
        
        for (int i = 0; i < time; i++) {
            UF[i] = i;
            val[i] = 1;
        }
        for (int i = 0; i < values.length; i++) {
            String a = equations[i][0];
            String b = equations[i][1];
            int index_a = map.get(a);
            int index_b = map.get(b);
            
            
            
            if (val[index_b] == 1) {
                UF[index_b] = index_a;
                val[index_b] = values[i];
            } else {
                UF[index_a] = UF[index_b];
                val[index_a] = val[index_b] / values[i];
            }
            
        }
        
        double[] ans = new double[queries.length];
        
        for (int i = 0; i < queries.length; i++) {
            if (!map.containsKey(queries[i][0]) || !map.containsKey(queries[i][1])) {
                ans[i] = -1.0;
            } else {
                int index_one = map.get(queries[i][0]);
                int index_two = map.get(queries[i][1]);
                double pro_one = 1;
                double pro_two = 1;
                while (UF[index_one] != index_one) {
                    pro_one *= val[index_one];
                    index_one = UF[index_one];
                }
                while (UF[index_two] != index_two) {
                    pro_two *= val[index_two];
                    index_two = UF[index_two];
                }
                if (index_one != index_two) {
                    ans[i] = -1.0;
                } else {
                    ans[i] = pro_two / pro_one;
                }
            }
        }
        return ans;
    }
    

    }


Log in to reply
 

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