Leetcode Study Day 44

Evaluate Division

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

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.

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]
 

Constraints:

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

Solution

For the solution, we use a nested map to record the graph. To be specific, we can imagine string a is a node, it map to string b, where the edge value is a/b, whcih is 1.5, it is the value that b mapped to. So we create a structure to store this nested map:

unordered_map <string, unordered_map<string, double>> 

Let me explain the code below:

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        // create the nested map with input equations
        unordered_map <string, unordered_map<string, double>> graph = createGraph(equations, values);
        // create the result vector
        vector<double> res;
        // for each query, we find the path product
        for (int i = 0; i < queries.size(); i++){
            if (queries[i][0] == queries[i][1] && graph.find(queries[i][0]) != graph.end())
                res.push_back(1.0); //Division of a number by itself
            else if (graph.find(queries[i][0]) == graph.end() || graph.find(queries[i][1]) == graph.end())
                res.push_back(-1.0); // if we cannot find the node in the graph
            else{
                // we find the path product and push it to the result vector
                double result = findPathProduct(graph, queries[i][0], queries[i][1]);
                res.push_back(result);
                }
        }
        return res;
    }

    // Create graph function
    unordered_map <string, unordered_map<string, double>> createGraph(vector<vector<string>>& equations,vector<double>& values){
        unordered_map <string, unordered_map<string, double>> graph;
        
        for (int i = 0; i < equations.size(); i++){
            double value = values[i];
            string A = equations[i][0];
            string B = equations[i][1];
            // store the value in the nested map
            graph[A][B] = value;
            // store the reverse value in the nested map
            graph[B][A] = 1.0 / value;
                
        }
        return graph;
    }

    // Find path product function
    double findPathProduct(unordered_map <string, unordered_map<string, double>>& graph, string& start, string& end){
        // create a set to store the visited node
        set<string> visited;
        return dfs(graph, start, end, 1.0, visited);
    }

    // DFS function
    double dfs(unordered_map<string, unordered_map<string, double>>& graph, const string& current, const string& end, double product, set<string>& visited){
        // if we have visited the node, we return -1.0
        if(visited.find(current)!= visited.end())
            return -1.0;
        // if we find the end node, we return the product
        if (current == end)
            return product;
        // we add the current node to the visited set
        visited.insert(current);
        // for each neighbor of the current node, we find the path product
        for (const auto& pair : graph[current]) {
            const string& neighbor = pair.first;
            double weight = pair.second;
            // we use dfs to find the path product
            double pathProduct = dfs(graph, neighbor, end, product * weight, visited);
            // if we find the path product, we return it
            if (pathProduct != -1.0)
                return pathProduct;
        }
        // if we cannot find the path product, we return -1.0
        visited.erase(current);
        return -1.0;
    }
};