399. Evaluate Division • Algorithm Solutions

1. Description

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [$A_i$, $B_i$] and values[i] represent the equation $A_i$ / $B_i$ = values[i]. Each $A_i$ or $B_i$ is a string that represents a single variable.
You are also given some queries, where queries[j] = [$C_j$, $D_j$] represents the jth query where you must find the answer for $C_j$ / $D_j$ = ?.
Return the answers to all queries. If a single answer cannot be determined, return -1.0.
Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.
Note: The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.

2. Example

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 ]
note: x is undefined => -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]

3. Constraints

1 <= equations.length <= 20
equations[i].length == 2
1 <= $A_i$.length, $B_i$.length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= $C_j$.length, $D_j$.length <= 5
$A_i$, $B_i$, $C_j$, $D_j$ consist of lower case English letters and digits.

4. Solutions

Breadth-First Search

class Solution {
public:
    vector<double> calcEquation(
        vector<vector<string>> &equations,
        vector<double> &values,
        vector<vector<string>> &queries) {
        const int n = equations.size();
        unordered_map<string, vector<pair<string, double>>> out;
        unordered_set<string> valid_exp;

        for (int i = 0; i < n; ++i) {
            out[equations[i][0]].push_back({equations[i][1], values[i]});
            out[equations[i][1]].push_back({equations[i][0], 1.0 / values[i]});

            valid_exp.insert(equations[i][0]);
            valid_exp.insert(equations[i][1]);
        }

        vector<double> results;
        for (const auto &query : queries) {
            results.push_back(calculate_equation(out, valid_exp, query));
        }

        return results;
    }

private:
    double calculate_equation(
        const unordered_map<string, vector<pair<string, double>>> &out,
        const unordered_set<string> &valid_exp,
        const vector<string> &query) {
        if (valid_exp.find(query[0]) == valid_exp.end() ||
            valid_exp.find(query[1]) == valid_exp.end()) {
            return -1;
        }

        if (query[0] == query[1]) {
            return 1;
        }

        unordered_set<string> visited;
        queue<pair<string, double>> to_visit;

        visited.insert(query[0]);
        to_visit.push({query[0], 1});
        while (!to_visit.empty()) {
            auto [exp1, value1] = to_visit.front();
            to_visit.pop();

            for (const auto &[exp2, value2] : out.at(exp1)) {
                if (exp2 == query[1]) {
                    return value1 * value2;
                }

                if (visited.find(exp2) == visited.end()) {
                    visited.insert(exp2);

                    to_visit.push({exp2, value1 * value2});
                }
            }
        }

        return -1;
    }
};