# 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

#### 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;
}
List < Edge > edges = map.get(from);
if (edges != null) {
for (Edge e: edges) {
if (visited.contains(e.to)) {
continue;
}
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;
}

List<Edge> edges = map.get(numerator);
if (edges != null) {
for (Edge e: edges) {
if (visited.contains(e.denominator)) {
continue;
}
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