LeetCode 399. Evaluate Division (Medium)

Description:

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:

Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].
           

The input is: vector<pair<string, string>> equations, vector& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 
           

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

Analysis:

Use DSU to create an undirected weighted graph. How to implement DSU when we deal with nodes whose labels are alphabets, please refer to 字母結點型DSU. The weight of an edge between a parent node P P P and a son node S S S is the value of V P / V S V_{P} / V_{S} VP​/VS​.

Here we also use path compression and rank-by-union strategies.

So if [ S 1 , S 2 ] [S_{1}, S_{2}] [S1​,S2​] is given, and node S 1 S_{1} S1​ and node S 2 S_{2} S2​ are both on the same connected part of the graph, to calculate the V S 1 / V S 2 V_{S_1} / V_{S2} VS1​​/VS2​, we just need to find the weights of paths between two nodes and the root node respectively. Here the two weights are V R / V S 1 V_{R} / V_{S1} VR​/VS1​ and V R / V S 2 V_{R} / V_{S2} VR​/VS2​ respectively. Next, calculate V R / V S 2 V R / V S 1 \frac{V_{R} / V_{S2}}{V_{R} / V_{S1}} VR​/VS1​VR​/VS2​​ to get the result of V S 1 / V S 2 V_{S_1} / V_{S2} VS1​​/VS2​.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    public static double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        DSU dsu = new DSU(equations);
        for(int i = 0; i < equations.size(); i++) {
            List<String> equation = equations.get(i);
            dsu.union(equation.get(0), equation.get(1), values[i]);
        }

        double[] rs = new double[queries.size()];

        for(int i = 0; i < queries.size(); i++) {
            rs[i] = dsu.calc(queries.get(i).get(0), queries.get(i).get(1));
        }
        return rs;
    }
}

class DSU {
    private Map<String, List> parent;
    private Map<String, Integer> rank;

    public DSU(List<List<String>> equations) {
        parent = new HashMap<>();
        rank = new HashMap<>();

        for(List<String>equation: equations) {
            for(String node: equation) {
                if(!parent.containsKey(node)) {
                    List tmp = new ArrayList();
                    tmp.add(node);
                    tmp.add(1.0);
                    parent.put(node, tmp);
                    rank.put(node, 1);
                }
            }
        }
    }

    public List find(String s) {
        List parentNode = parent.get(s);
        String parentLabel = (String)parentNode.get(0);
        double value = (double)parentNode.get(1);

        if(!s.equals(parentLabel)) {
            parentNode = find(parentLabel);
            parentLabel = (String)parentNode.get(0);
            double new_value = (double)parentNode.get(1) * value;

            List newParentNode = new ArrayList();
            newParentNode.add(parentLabel);
            newParentNode.add(new_value);
            parent.put(s, newParentNode);

            return newParentNode;
        }else {
            return parentNode;
        }
    }

    public void union(String s1, String s2, double value) {
        List s1R = parent.get(s1);
        String s1RLabel = (String)s1R.get(0);
        double v1 = (double)s1R.get(1);

        List s2R = parent.get(s2);
        String s2RLabel = (String)s2R.get(0);
        double v2 = (double)s2R.get(1);

        if(s1RLabel.equals(s2RLabel)) {
            return;
        }else{
            if(rank.get(s1RLabel) < rank.get(s2RLabel)) {
                List parentNode = new ArrayList();
                parentNode.add(s2RLabel);
                double newValue = v2 / value;
                parentNode.add(newValue);
                parent.put(s1RLabel, parentNode);
            }else if(rank.get(s1RLabel) > rank.get(s2RLabel)) {
                List parentNode = new ArrayList();
                parentNode.add(s1RLabel);
                double newValue = v1 * value;
                parentNode.add(newValue);
                parent.put(s2RLabel, parentNode);
            }else{
                List parentNode = new ArrayList();
                parentNode.add(s1RLabel);
                double newValue = v1 * value;
                parentNode.add(newValue);
                parent.put(s2RLabel, parentNode);
                rank.put(s1RLabel, rank.get(s1RLabel)+1);
            }
        }
    }

    public double calc(String s1, String s2) { ;
        if(parent.containsKey(s1) && parent.containsKey(s2)) {
            List s1R = find(s1);
            String s1RLabel = (String)s1R.get(0);
            double v1 = (double)s1R.get(1);

            List s2R = find(s2);
            String s2RLabel = (String)s2R.get(0);
            double v2 = (double)s2R.get(1);

            if(s1RLabel.equals(s2RLabel)) {
                return v2 / v1;
            }else{
                return -1.0;
            }
        }
        return -1.0;
    }
}