 # 399. Evaluate Division

Jan 16th, 2022
793
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /*
2.  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.
3.
4.  You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.
5.
6.  Return the answers to all queries. If a single answer cannot be determined, return -1.0.
7.
8. 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.
9.
10.
11. constraints:
12.     0 < values[i]
13.
14.
15. - example:
16.   input:
17.     equations = [["a","b"],["b","c"]]
18.     values    = [2.0,3.0]
19.     queries   = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
20.   output:
21.     [6.00000,0.50000,-1.00000,1.00000,-1.00000]
22. */
23.
24. /*
25. notes:
26.
27. if the graph is stored as a map<string, string>
28. for each query the algorithm might go through all the names
29. so it's better to map all the names to number at first
30.
31. building a graph:
32.   time:     O(#equations)
33.   memory:   O(#equations)
34.
35. offline:
36.   precalcute all the possible results
37.   precalc time: O(#equations * #variables) - DFS for each vertex
38.   query time:   O(1)
39.   space:        O(#variables^2)
40.
41. online:
43.   precalc time: O(#equations)
44.   query time:   O(#equations)
45.   space:        O(#equations)
46. */
47.
48. /*
49. tricky tests:
50.     going backwards
51.     same variable (A/A = ?)
52.     X/X where X wasn't in equations: -1.
53. */
54.
55. class Solution {
56. public:
57.     /*
58.     approach:
59.         store equations as a weighted oriented graph (map<string, Edge>)
60.         for each equations add two edges (special cases with loops)
61.
62.         make a DFS for the source vertex until we reach the target one
63.     */
64.
65.     unordered_map<string, int> var_code;
66.     vector<unordered_map<int, double>> g;
67.
68.     double v_div_target(int v, int target, vector<bool>& visited) {
69.         if (visited[v]) {
70.             return -1.;
71.         }
72.         visited[v] = true;
73.
74.         if (v == target) {
75.             return 1.;
76.         }
77.
78.         for (auto [to, val] : g[v]) {
79.             double to_div_target = v_div_target(to, target, visited);
80.             if (to_div_target != -1.) {
81.                 // v / to = val
82.                 // to / target = to_div_target
83.                 // -> v / target = val * to_div_target
84.                 return val * to_div_target;
85.             }
86.         }
87.         return -1.;
88.     }
89.
90.     vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
91.         for (int i = 0; i < equations.size(); ++i) {
92.             auto& eq = equations[i];
93.             for (int j = 0; j < 2; ++j) {
94.                 const string& var_name = eq[j];
95.                 if (!var_code.count(var_name)) {
96.                     int var_i = var_code.size();
97.                     var_code[var_name] = var_i;
98.                 }
99.             }
100.
101.             double val = values[i];
102.             int code1 = var_code[eq];
103.             int code2 = var_code[eq];
104.             if (code1 == code2) {
105.                 continue;
106.             }
107.             g.resize(var_code.size());
108.             g[code1][code2] = val;
109.             g[code2][code1] = 1. / val;
110.         }
111.
112.         vector<double> res;
113.         vector<bool> visited(var_code.size(), false);
114.         for (auto& query : queries) {
115.             int v = (var_code.count(query) ? var_code[query] : -1);
116.             int t = (var_code.count(query) ? var_code[query] : -1);
117.             visited.assign(visited.size(), false);
118.
119.             double cur_res = ((v == -1 || t == -1) ? -1. : v_div_target(v, t, visited));
120.             res.push_back(cur_res);
121.         }
122.         return res;
123.     }
124. };
125.