JAVA, 35 lines, O(1) for each query pair, nlogn for worst case preprocess time.


  • 0
    I

    Divide the strings in equations into connected sets.
    If str1 and str2 are in same equation, they are connected.
    Assign values to strings in a set based on the equations:
    E.g. equation: a/b = V,

    1. if a is in Set1 as Va and b is not in any set, then add b to Set1 as Va/V.
    2. if b is in Set1 as Vb and a is not in any set, then add a to Set1 as Vb*V.
    3. a,b not in any set, create new set, add a as V, b as 1.0.
    4. if a is in Set1 as Va and b is in Set2 as Vb, join two sets.
      (to achieve nlogn, need to join small to big, but no difference for existing TCs, n is # of equations)

    Query: simply return Vx/Vy, if x and y are in the same set.

    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        Map<String, Integer> sets = new HashMap<>();
        Map<String, Double> vals = new HashMap<>();
        List<List<String>> list = new ArrayList<>();
        for (int i = 0; i < equations.length; ++i) {
            String a = equations[i][0], b = equations[i][1];
            Integer setA = sets.get(a), setB = sets.get(b);
            if (setA == null && setB == null) {
                sets.put(a, list.size());
                sets.put(b, list.size());
                vals.put(a, values[i]);
                vals.put(b, 1.0);
                list.add(new LinkedList<>(Arrays.asList(a, b)));
            } else if (setB == null) {
                sets.put(b, setA);
                vals.put(b, vals.get(a) / values[i]); // not consider 0.0
                list.get(setA).add(b);
            } else if (setA == null) {
                sets.put(a, setB);
                vals.put(a, vals.get(b) * values[i]);
                list.get(setB).add(a);
            } else if (!setA.equals(setB)) {
                double factor = vals.get(a) / values[i] / vals.get(b);
                for (String str : list.get(setB)) {
                    sets.put(str, setA);
                    vals.put(str, vals.get(str) * factor);
                }
            }
        }
        double[] ans = new double[queries.length];
        for (int i = 0; i < queries.length; ++i) {
            Integer setA = sets.get(queries[i][0]), setB = sets.get(queries[i][1]);
            if (setA != null && setA.equals(setB)) ans[i] = vals.get(queries[i][0]) / vals.get(queries[i][1]);
            else ans[i] = -1.0;
        }
        return ans;
    }
    

Log in to reply
 

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