aboutsummaryrefslogtreecommitdiff
path: root/evaluate_division.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'evaluate_division.cpp')
-rw-r--r--evaluate_division.cpp63
1 files changed, 63 insertions, 0 deletions
diff --git a/evaluate_division.cpp b/evaluate_division.cpp
new file mode 100644
index 0000000..7bda627
--- /dev/null
+++ b/evaluate_division.cpp
@@ -0,0 +1,63 @@
+#include "leetcode.h"
+
+class Solution {
+public:
+ vector<double> calcEquation(vector<vector<string>> &equations,
+ vector<double> &values,
+ vector<vector<string>> &queries) {
+ vector<double> ans;
+ map<string, double> mp;
+ map<string, vector<string>> graph;
+ for (int i = 0; i < equations.size(); i++) {
+ string u = equations[i][0], v = equations[i][1];
+ mp[u + "->" + v] = values[i];
+ mp[v + "->" + u] = 1 / values[i];
+ graph[u].push_back(v);
+ graph[v].push_back(u);
+ }
+ for (int i = 0; i < queries.size(); i++) {
+ string start = queries[i][0], end = queries[i][1];
+ if (graph.find(start) == graph.end() || graph.find(end) == graph.end()) {
+ ans.push_back(-1);
+ } else {
+ double val = 1;
+ map<string, int> visited;
+ bool found = false;
+ if (start == end)
+ found = true;
+ else
+ dfs(start, end, mp, graph, val, visited, found);
+ if (found == true)
+ ans.push_back(val);
+ else
+ ans.push_back(-1);
+ }
+ }
+ return ans;
+ }
+
+private:
+ void dfs(string start, string end, map<string, double> &mp,
+ map<string, vector<string>> &graph, double &val,
+ map<string, int> &visited, bool &found) {
+ visited[start] = 1;
+ if (found == true)
+ return;
+ for (auto child : graph[start]) {
+ if (visited[child] != 1) {
+ val *= mp[start + "->" + child];
+ if (end == child) {
+ found = true;
+ return;
+ }
+ dfs(child, end, mp, graph, val, visited, found);
+ if (found == true)
+ return;
+ else
+ val /= mp[start + "->" + child];
+ }
+ }
+ }
+};
+
+int main() {}