leetcode 399 - Evaluate Division

https://leetcode.com/problems/evaluate-division/

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Example 1:

Input: equations = [[“a”,”b”],[“b”,”c”]], values = [2.0,3.0], queries = [[“a”,”c”],[“b”,”a”],[“a”,”e”],[“a”,”a”],[“x”,”x”]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation:
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 ]
Example 2:

Input: equations = [[“a”,”b”],[“b”,”c”],[“bc”,”cd”]], values = [1.5,2.5,5.0], queries = [[“a”,”c”],[“c”,”b”],[“bc”,”cd”],[“cd”,”bc”]]
Output: [3.75000,0.40000,5.00000,0.20000]
Example 3:

Input: equations = [[“a”,”b”]], values = [0.5], queries = [[“a”,”b”],[“b”,”a”],[“a”,”c”],[“x”,”y”]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

Constraints:

1 <= equations.length <= 20
equations[i].length == 2
1 <= Ai.length, Bi.length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= Cj.length, Dj.length <= 5
Ai, Bi, Cj, Dj consist of lower case English letters and digits.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
unordered_map<string, vector<pair<string, double>>> graph;

int n = equations.size();
for (int i = 0; i < n; i++) {
string &a = equations[i][0];
string &b = equations[i][1];

graph[a].push_back({b, 1.0/values[i]});
graph[b].push_back({a, values[i]});
}

vector<double> result;

for (auto &query : queries) {
if (graph.count(query[0]) == 0 || graph.count(query[1]) == 0)
result.push_back(-1.0);
else
result.push_back(bfs(graph, query[1], query[0]));
}

return result;
}

double bfs(unordered_map<string, vector<pair<string, double>>> &graph, string &a, string &b) {
queue<pair<string, double>> q;
unordered_set<string> seen;

q.push({a, 1.0});
seen.insert(a);

while (!q.empty()) {
int n = q.size();

for (int i = 0; i < n; i++) {
auto p = q.front(); q.pop();
if (p.first == b)
return p.second;

auto &edges = graph[p.first];
for (auto &e : edges) {
if (seen.count(e.first)) continue;

q.push({e.first, p.second * e.second});
seen.insert(e.first);
}
}
}

return -1.0;
}
};