Evaluate Division
Weighted Directed Graph -> Find Path Weight
Medium
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 & Analysis
把问题转化为图 Weighted Directed Graph，然后因为不同的路径到达目标path value应该是一样的，因此只需要用DFS找到一个路径即可返回。
建Adjacency List的时候，因为这是带权重的有向图，要顺便添加反向的edge，也就是1.0/value。
Version 2 - DFS
class Solution {
class Edge {
String from;
String to;
double value;
Edge(String from, String to, double value) {
this.from = from;
this.to = to;
this.value = value;
}
}
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
// Build graph
HashMap<String, List<Edge>> map = buildGraph(equations, values);
double[] result = new double[queries.length];
// Calculate result for each query by searching in the graph
int idx = 0;
for (String[] query: queries) {
if (!map.containsKey(query[0])) {
result[idx] = -1.0;
} else {
String n = query[0];
String d = query[1];
HashSet<String> visited = new HashSet < > ();
double val = dfs(map, visited, 1.0, n, d);
result[idx] = val;
}
idx++;
}
return result;
}
// Build graph with adjacency list
private HashMap<String, List<Edge>> buildGraph(String[][] equations, double[] values) {
HashMap<String, List<Edge>> map = new HashMap<>();
for (int i = 0; i < equations.length; i++) {
// convert input equation to edge with value
if (!map.containsKey(equations[i][0])) {
map.put(equations[i][0], new ArrayList<Edge>());
}
map.get(equations[i][0]).add(new Edge(equations[i][0], equations[i][1], values[i]));
// reverse order to store inverse value for edge
if (!map.containsKey(equations[i][1])) {
map.put(equations[i][1], new ArrayList<Edge>());
}
map.get(equations[i][1]).add(new Edge(equations[i][1], equations[i][0], 1.0 / values[i]));
}
return map;
}
// Recursively search a path from numerator (from) to denominator (to); return -1.0 if not found
private double dfs(HashMap<String, List<Edge>> map, HashSet<String> visited, double pathVal, String from, String to) {
if (from.equals(to)) {
return pathVal;
}
visited.add(from);
List < Edge > edges = map.get(from);
if (edges != null) {
for (Edge e: edges) {
if (visited.contains(e.to)) {
continue;
}
visited.add(e.to);
double value = dfs(map, visited, pathVal * e.value, e.to, to);
if (value != -1.0) {
return value;
}
}
}
return -1.0;
}
}Version 1 - DFS (2 ms, faster than 64.65%)
class Solution {
class Edge {
String numerator;
String denominator;
double value;
Edge (String numerator, String denominator, double value) {
this.numerator = numerator;
this.denominator = denominator;
this.value = value;
}
// For debugging
String printString() {
return numerator + " - " + denominator + ": " + value;
}
}
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
// build adjacency list
HashMap<String, List<Edge>> map = new HashMap<>();
for (int i = 0; i < equations.length; i++) {
// convert input equation to edge with value
if (!map.containsKey(equations[i][0])) {
map.put(equations[i][0], new ArrayList<Edge>());
}
map.get(equations[i][0]).add(new Edge(equations[i][0], equations[i][1], values[i]));
// reverse order to store inverse value for edge
if (!map.containsKey(equations[i][1])) {
map.put(equations[i][1], new ArrayList<Edge>());
}
map.get(equations[i][1]).add(new Edge(equations[i][1], equations[i][0], 1.0 / values[i]));
}
double[] result = new double[queries.length];
int idx = 0;
for (String[] query: queries) {
if (!map.containsKey(query[0])) {
result[idx] = -1.0;
} else {
String n = query[0];
String d = query[1];
HashSet<String> visited = new HashSet<>();
double val = dfs(map, visited, 1.0, n, d);
result[idx] = val;
}
idx++;
}
return result;
}
private double dfs(HashMap<String, List<Edge>> map, HashSet<String> visited, double val, String numerator, String denominator) {
if (numerator.equals(denominator)) {
return val;
}
visited.add(numerator);
List<Edge> edges = map.get(numerator);
if (edges != null) {
for (Edge e: edges) {
if (visited.contains(e.denominator)) {
continue;
}
visited.add(e.denominator);
double value = dfs(map, visited, val * e.value, e.denominator, denominator);
if (value != -1.0) {
return value;
}
}
}
return - 1.0;
}
// For debugging
private void printAdjacencyList (HashMap<String, List<Edge>> map) {
for (Map.Entry<String, List<Edge>> entry: map.entrySet()) {
List<Edge> v = entry.getValue();
for (Edge e: v) {
System.out.println(e.printString());
}
}
}
}Reference
https://leetcode.com/problems/evaluate-division/discuss/171649/1ms-DFS-with-Explanations
Last updated