## Evaluate Division

• Time:O(e + eq) \to O(e + q), where e = |\texttt{equations}| and q = |\texttt{queries}|
• Space:O(e)

## C++

class Solution {
public:
vector<double> calcEquation(vector<vector<string>>& equations,
vector<double>& values,
vector<vector<string>>& queries) {
vector<double> ans;
// graph[A][B] := A / B
unordered_map<string, unordered_map<string, double>> graph;

for (int i = 0; i < equations.size(); ++i) {
const string& A = equations[i][0];
const string& B = equations[i][1];
graph[A][B] = values[i];
graph[B][A] = 1 / values[i];
}

for (const auto& q : queries) {
const string& A = q[0];
const string& C = q[1];
if (!graph.count(A) || !graph.count(C))
ans.push_back(-1);
else
ans.push_back(divide(graph, A, C, unordered_set<string>()));
}

return ans;
}

private:
// return A / C
double divide(
const unordered_map<string, unordered_map<string, double>>& graph,
const string& A, const string& C, unordered_set<string>&& seen) {
if (A == C)
return 1.0;

seen.insert(A);

// value := A / B
for (const auto& [B, value] : graph.at(A)) {
if (seen.count(B))
continue;
const double res = divide(graph, B, C, move(seen));  // B / C
if (res > 0)                                         // valid result
return value * res;  // A / C = (A / B) * (B / C)
}

return -1;  // invalid result
}
};


## JAVA

class Solution {
public double[] calcEquation(List<List<String>> equations, double[] values,
List<List<String>> queries) {
double[] ans = new double[queries.size()];
// graph.get(A).get(B) := A / B
Map<String, Map<String, Double>> graph = new HashMap<>();

// construct the graph
for (int i = 0; i < equations.size(); ++i) {
final String A = equations.get(i).get(0);
final String B = equations.get(i).get(1);
graph.putIfAbsent(A, new HashMap<>());
graph.putIfAbsent(B, new HashMap<>());
graph.get(A).put(B, values[i]);
graph.get(B).put(A, 1.0 / values[i]);
}

for (int i = 0; i < queries.size(); ++i) {
final String A = queries.get(i).get(0);
final String C = queries.get(i).get(1);
if (!graph.containsKey(A) || !graph.containsKey(C))
ans[i] = -1.0;
else
ans[i] = divide(graph, A, C, new HashSet<>());
}

return ans;
}

// return A / C
private double divide(Map<String, Map<String, Double>> graph, final String A, final String C,
Set<String> seen) {
if (A.equals(C))
return 1.0;

for (final String B : graph.get(A).keySet()) {
if (seen.contains(B))
continue;
final double res = divide(graph, B, C, seen); // B / C
if (res > 0)                                  // valid result
return graph.get(A).get(B) * res;           // A / C = (A / B) * (B / C)
}

return -1.0; // invalid result
}
}


## Python

class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
ans = []
# graph[A][B] := A / B
graph = defaultdict(dict)

for (A, B), value in zip(equations, values):
graph[A][B] = value
graph[B][A] = 1 / value

# return A / C
def devide(A: str, C: str, seen: Set[str]) -> float:
if A == C:
return 1.0

# value := A / B
for B, value in graph[A].items():
if B in seen:
continue
res = devide(B, C, seen)  # B / C
if res > 0:  # valid
return value * res  # (A / B) * (B / C) = A / C

return -1.0  # invalid

for A, C in queries:
if A not in graph and C not in graph:
ans.append(-1.0)
else:
ans.append(devide(A, C, set()))

return ans