399

399. Evaluate Division (Medium)

You are given equations 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.

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

 

Example 1:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation: 
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 ]

Example 2:

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]

Example 3:

Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

 

Constraints:

• 1 <= equations.length <= 20
• equations[i].length == 2
• 1 <= equations[i][0], equations[i][1] <= 5
• values.length == equations.length
• 0.0 < values[i] <= 20.0
• 1 <= queries.length <= 20
• queries[i].length == 2
• 1 <= queries[i][0], queries[i][1] <= 5
• equations[i][0], equations[i][1], queries[i][0], queries[i][1] consist of lower case English letters and digits.

Related Topics:
Union Find, Graph

Solution 1.

// OJ: https://leetcode.com/problems/evaluate-division/
// Author: github.com/lzl124631x
class Solution {
private:
    unordered_map<string, unordered_map<string, double>> m;
    double dfs(string from, string to, set<string> &visited) {
        if (m[from].count(to)) return m[from][to];
        for (auto p : m[from]) {
            if (visited.count(p.first)) continue;
            visited.insert(p.first);
            double v = dfs(p.first, to, visited);
            if (v != -1) return p.second * v;
        }
        return -1;
    }
public:
    vector<double> calcEquation(vector<vector<string>> &equations, vector<double>& values, vector<vector<string>> queries) {
        for (int i = 0; i < equations.size(); ++i) {
            auto &e = equations[i];
            m[e[0]][e[1]] = values[i];
            m[e[1]][e[0]] = 1 / values[i];
        }
        vector<double> ans;
        for (auto q : queries) {
            set<string> visited;
            auto &a = q[0], &b = q[1];
            if (!m.count(a) || !m.count(b)) ans.push_back(-1);
            else if (a == b) ans.push_back(1);
            else ans.push_back(dfs(a, b, visited));
        }
        return ans;
    }
};