399. Evaluate Division
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<double>& values, vector<pair<string, string>> queries
, where equations.size() == values.size()
, and the values are positive. This represents the equations. Return vector<double>
.
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.
Solution
(1) Java
class Solution {
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
Map<String, List<String>> eqs = new HashMap<>();
Map<String, List<Double>> vals = new HashMap<>();
int idx = 0;
for (String[] equation : equations) {
if (!eqs.containsKey(equation[0])) {
eqs.put(equation[0], new ArrayList<String>());
vals.put(equation[0], new ArrayList<Double>());
}
eqs.get(equation[0]).add(equation[1]);
vals.get(equation[0]).add(values[idx]);
if (!eqs.containsKey(equation[1])) {
eqs.put(equation[1], new ArrayList<String>());
vals.put(equation[1], new ArrayList<Double>());
}
eqs.get(equation[1]).add(equation[0]);
vals.get(equation[1]).add(1.0/values[idx]);
idx++;
}
double[] rst = new double[queries.length];
Arrays.fill(rst, -1.0);
for (int i = 0; i < queries.length; i++) {
String[] query = queries[i];
if (query[0].equals(query[1]) && eqs.containsKey(query[0])) {
rst[i] = 1.0;
continue;
}
dfs(query, eqs, vals, rst, i, 1, query[1], query[0]);
}
return rst;
}
private boolean dfs(String[] query , Map<String, List<String>> eqs, Map<String, List<Double>> vals, double[] rst, int idx, double prevVal, String target, String parent) {
if (!eqs.containsKey(query[0])) {
return false;
}
List<String> denomitors = eqs.get(query[0]);
if (denomitors.indexOf(target) != -1) {
rst[idx] = prevVal*(vals.get(query[0]).get(denomitors.indexOf(target)));
return true;
}
if (!eqs.containsKey(query[1])) {
return false;
}
for (int i = 0; i < denomitors.size(); i++) {
String nd = denomitors.get(i);
if (nd.equals(parent)) {
continue;
}
String[] query2 = new String[] {nd, query[1]};
if (dfs(query2, eqs, vals, rst, idx, prevVal*(vals.get(query[0]).get(i)), target,query[0])) {
return true;
}
}
return false;
}
}
If using UF:
class Solution {
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
if(equations==null || equations.length==0) return new double [] {};
Map<String, String>root=new HashMap<>();
Map<String, Double>map=new HashMap<>();
for (int i=0;i<equations.length;i++){
String x1=equations[i][0], x2=equations[i][1];
root.putIfAbsent(x1, x1);
root.putIfAbsent(x2, x2);
map.putIfAbsent(x1, 1.0);
map.putIfAbsent(x2, 1.0);
String r1=find(root, x1);
String r2=find(root, x2);
root.put(r2, r1);
map.put(r2, map.get(x1)*values[i]/map.get(x2));
}
double[] res=new double[queries.length];
for (int i=0;i<queries.length;i++){
res[i]=-1.0;
String x1=queries[i][0], x2=queries[i][1];
if (!root.containsKey(x1) || !root.containsKey(x2)) continue;
String r1=find(root, x1);
String r2=find(root, x2);
if (r1.equals(r2))
res[i]=get(root, map, x2) / get(root, map, x1);
}
return res;
}
private String find(Map<String, String>root, String var){
if (root.get(var).equals(var)) return var;
return find(root, root.get(var));
}
private double get(Map<String, String>root, Map<String, Double>map, String var){
String r=root.get(var);
double result=map.get(var);
if (r.equals(var)) return result;
return result*get(root, map, r);
}
}
(2) Python
(3) Scala