399. Evaluate Division (Medium)

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.

Solution 1: DFS 0ms

class Solution {
    double dfs (string s, string t, unordered_map<string, unordered_map<string, double>>& m, unordered_set<string> &visited, double val) {
        if (m[s].count(t)) return val*m[s][t];

        for (auto& p: m[s]) {
            if (visited.count(p.first) == 0) {
                visited.insert(p.first);
                double tmp = dfs(p.first, t, m, visited, val*p.second);
                if (tmp != -1.0)  return tmp;
            }
        }
        return -1.0;
    }
public:
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        unordered_map<string, unordered_map<string, double>> m;
        vector<double> res(queries.size(), -1);
        for (int i = 0; i < equations.size(); ++i) {
            string s = equations[i].first, t = equations[i].second;
            m[s][t] = values[i];
            m[t][s] = 1/values[i];
        }

        for (int i = 0; i < queries.size(); ++i) {
            string s = queries[i].first, t = queries[i].second;
            if (m.count(s) && m.count(t)) {
                if (s == t) res[i] = 1.0;
                else {
                    unordered_set<string> visited;
                    visited.insert(s);
                    res[i] = dfs(s, t, m, visited, 1.0);
                    // add answer to map for future use
                    if (res[i] != -1.0) {
                        m[s][t] = res[i];
                        m[t][s] = 1/res[i];
                    }
                }
            } 
        }
        return res;
    }
};

Solution 2: BFS 3ms

此题还有迭代的写法，用邻接列表的表示方法建立了一个图，然后进行bfs搜索，需要用queue来辅助运算，参见代码如下：

class Solution {
public:
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        unordered_map<string, unordered_map<string, double>> m;
        vector<double> res(queries.size(), -1);
        for (int i = 0; i < equations.size(); ++i) {
            string s = equations[i].first, t = equations[i].second;
            m[s][t] = values[i];
            m[t][s] = 1/values[i];
        }

        for (int i = 0; i < queries.size(); ++i) {
            string s = queries[i].first, t = queries[i].second;
            if (m.count(s) && m.count(t)) {
                if (s == t) res[i] = 1.0;
                else if (m[s].count(t)) res[i] = m[s][t];
                else {
                    queue<pair<string, double>> q;
                    unordered_set<string> visited{s};
                    q.push({s, 1.0});
                    while (!q.empty()) {
                        auto f = q.front(); q.pop();
                        //  find path
                        if (f.first == t) {
                            res[i] = f.second;
                            // store result to map for future use
                            m[s][t] = f.second;
                            m[t][s] = 1/f.second;
                            break;
                        }
                        for (auto& p: m[f.first]) {
                            if (visited.count(p.first) == 0) {
                                visited.insert(p.first);
                                q.push({p.first, p.second*f.second});
                            }

                        }
                    }
                }
            } 
        }
        return res;
    }
};

Solution 3: Union-find