Evaluate Division

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

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

Example:

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 ].

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<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.

Thoughts

给一系列变量之间相除的结果，返回给定两个变量之间相除的结果。根据例子写一下就知道比如求a/c, 需要a/b * b/c, 要先找到a/b, 再找到b/c 因此是道搜索题。 别忘了divisor/dividend = 1/（dividend/divisor）也加入已知eqs中。

Code

/*
 * @lc app=leetcode id=399 lang=cpp
 *
 * [399] Evaluate Division
 */
class Solution {
private:
    double dfs(const string &a, const string &t, unordered_map<string, unordered_map<string, double>> &m, unordered_set<string> &visited) {
        if (!m.count(a) || !m.count(t)) return -1;
        if (a == t) return 1;
        visited.insert(a);
        for (const auto &p : m[a]) {
            const string &b = p.first;
            if (!visited.count(b)) {
                const auto r = dfs(b, t, m, visited);
                if (r != -1) return r * m[a][b];
            }
        }
        return -1;
    }
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string, unordered_map<string, double>> m;
        for (int i = 0; i < equations.size(); ++i) {
            const auto &eq = equations[i];
            m[eq[0]][eq[1]] = values[i];
            m[eq[1]][eq[0]] = 1 / values[i]; 
        } 
        const int N = queries.size();
        vector<double> res(N);
        unordered_set<string> visited;
        for (int i = 0; i < N; ++i) {
            res[i] = dfs(queries[i][0], queries[i][1], m, visited);
            visited.clear();
        }
        return res;
    }
};

Analysis

Errors: 1. dfs在判断结果是否-1前就乘了

query的每次时间复杂度O(N), N为equations数目.