|
| 1 | +// Source : https://leetcode.com/problems/evaluate-division/ |
| 2 | +// Author : Hao Chen |
| 3 | +// Date : 2016-11-05 |
| 4 | + |
| 5 | +/*************************************************************************************** |
| 6 | + * |
| 7 | + * Equations are given in the format A / B = k, where A and B are variables |
| 8 | + * represented as strings, and k is a real number (floating point number). Given some |
| 9 | + * queries, return the answers. If the answer does not exist, return -1.0. |
| 10 | + * |
| 11 | + * Example: |
| 12 | + * Given a / b = 2.0, b / c = 3.0. queries are: a / c = ?, b / a = ?, a / e = ?, a |
| 13 | + * / a = ?, x / x = ? . return [6.0, 0.5, -1.0, 1.0, -1.0 ]. |
| 14 | + * |
| 15 | + * The input is: vector<pair<string, string>> equations, vector<double>& values, |
| 16 | + * vector<pair<string, string>> queries , where equations.size() == values.size(), and |
| 17 | + * the values are positive. This represents the equations. Return vector<double>. |
| 18 | + * |
| 19 | + * According to the example above: |
| 20 | + * equations = [ ["a", "b"], ["b", "c"] ], |
| 21 | + * values = [2.0, 3.0], |
| 22 | + * queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. |
| 23 | + * |
| 24 | + * The input is always valid. You may assume that evaluating the queries will result in |
| 25 | + * no division by zero and there is no contradiction. |
| 26 | + ***************************************************************************************/ |
| 27 | + |
| 28 | +classSolution { |
| 29 | +private: |
| 30 | +booldfs( unordered_map<string, unordered_map<string,double>>& m, |
| 31 | + unordered_map<string,bool>& visited, |
| 32 | + string& start, string& end,double& res ) { |
| 33 | + |
| 34 | +if ( m.find(start) == m.end() || m.find(end) == m.end() )returnfalse; |
| 35 | +if ( start == end )returntrue; |
| 36 | + |
| 37 | +for (auto it = m[start].begin(); it != m[start].end(); ++it) { |
| 38 | + |
| 39 | +auto key = it->first; |
| 40 | +auto value = it->second; |
| 41 | + |
| 42 | +// already visited, skip it. |
| 43 | +if (visited.find(key) != visited.end() ) { |
| 44 | +continue; |
| 45 | + } |
| 46 | + |
| 47 | + visited[key] =true; |
| 48 | +double old = res; |
| 49 | + res *= value; |
| 50 | + |
| 51 | +if (dfs(m, visited, key, end, res)) { |
| 52 | +returntrue; |
| 53 | + } |
| 54 | +//didn't find the result, reset the current result, and go to next one |
| 55 | + res = old; |
| 56 | + visited.erase(key); |
| 57 | + } |
| 58 | + |
| 59 | +returnfalse; |
| 60 | + } |
| 61 | +public: |
| 62 | + vector< double> calcEquation(vector<pair<string, string>> equations, |
| 63 | + vector<double>& values, |
| 64 | + vector<pair<string, string>> queries) { |
| 65 | + |
| 66 | + unordered_map<string, unordered_map<string,double>> m; |
| 67 | +for(int i=0; i<equations.size(); i++) { |
| 68 | +auto first = equations[i].first; |
| 69 | +auto second = equations[i].second; |
| 70 | + m[first][second] = values[i]; |
| 71 | + m[second][first] =1.0 / values[i]; |
| 72 | + } |
| 73 | + |
| 74 | + |
| 75 | + vector<double> result; |
| 76 | +for(auto q : queries) { |
| 77 | + string start = q.first; |
| 78 | + string end = q.second; |
| 79 | + |
| 80 | + unordered_map<string,bool> visited; |
| 81 | + visited[start] =true; |
| 82 | +double res =1.0; |
| 83 | + |
| 84 | +if(dfs(m, visited, start, end, res)) { |
| 85 | + result.push_back(res); |
| 86 | + }else { |
| 87 | + result.push_back(-1.0); |
| 88 | + } |
| 89 | + } |
| 90 | + |
| 91 | +return result; |
| 92 | + } |
| 93 | +}; |