399. Evaluate Division

Equations are given in the formatA / B = k, whereAandBare variables represented as strings, andkis a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return-1.0.

Example:
Givena / 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 ].

The input is:vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries, whereequations.size() == values.size(), and the values are positive. This represents the equations. Returnvector<double>.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

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

S：hashmap+recursion

divisor: 除数 dividend：被除数

用hashmap存储每个dividen的divisor，注意正反向都要存

class Solution {
public:
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        vector<double> result;
        for (int i = 0; i < equations.size(); ++i) {
            map[equations[i].first][equations[i].second] = values[i];
            if (values[i] != 0) map[equations[i].second][equations[i].first] = 1.0 / values[i];
        }
        for (const auto& p : queries) {
            unordered_set<string> visited;
            double cur_result;
            if (map.find(p.first) != map.end() && dfs(values, cur_result, 1, p.first, p.second, visited)) {
                result.push_back(cur_result);
            } else {
                result.push_back(-1.0);
            }
        }
        return result;
    } 

private:
    unordered_map<string, unordered_map<string, double>> map;
    bool dfs(vector<double>& values, double& result, double pre, string cur, string divisor, unordered_set<string>& visited) {
        if (cur == divisor) {
            result = 1.0;
            return true;
        }
        for (const auto& i : map[cur]) {
            if (i.first == divisor) {
                result = pre * i.second;
                return true;
            }
            if (visited.find(i.first) == visited.end() && map.find(i.first) != map.end()) {
                visited.insert(i.first);
                if(dfs(values, result, pre * i.second, i.first, divisor, visited)) {
                    return true;
                }
            }
        }
        return false;
    }
};