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
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:
public class Solution {
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
Map<String, Map<String, Double>> graph = new HashMap<>();
for(int i=0; i<equations.length; i++){
if(!graph.containsKey(equations[i][0])) graph.put(equations[i][0], new HashMap<>());
graph.get(equations[i][0]).put(equations[i][1], values[i]);
if(!graph.containsKey(equations[i][1])) graph.put(equations[i][1], new HashMap<>());
graph.get(equations[i][1]).put(equations[i][0], 1.0/values[i]);
}
double[] ans = new double[queries.length];
for(int i=0; i<queries.length; i++){
Queue<String> q = new LinkedList<>();
Queue<Double> a = new LinkedList<>();
Set<String> s = new HashSet<>();
q.offer(queries[i][0]);
a.offer(1.0);
s.add(queries[i][0]);
while(!q.isEmpty()){
String numerator = q.poll();
Double cur = a.poll();
if(numerator.equals(queries[i][1])){
ans[i] = cur;
break;
}
if(!graph.containsKey(numerator)) continue;
for(String denominator : graph.get(numerator).keySet()){
if(!s.contains(denominator)){
s.add(denominator);
q.offer(denominator);
a.offer(cur*graph.get(numerator).get(denominator));
}
}
}
if(!graph.containsKey(queries[i][0]) || !s.contains(queries[i][1])) ans[i] = -1.0;
}
return ans;
}
}