Description

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] andvalues[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 forCj / 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.

 

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]

 

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.

Thinking

Let's think about how we calculate a fraction:

If we have $\frac{A}{B}$$\frac{A}{B}$ and $\frac{B}{C}$$\frac{B}{C}$, then clearly, we could also have $\frac{C}{B}$$\frac{C}{B}$, $\frac{B}{A}$$\frac{B}{A}$, $\frac{A}{C}$$\frac{A}{C}$, $\frac{C}{A}$$\frac{C}{A}$, since $\frac{A}{C}=\frac{A}{B}\times \frac{B}{C}$$\frac{A}{C} = \frac{A}{B} \times \frac{B}{C}$

This is more like a chain, a path to follow. If we want to get A/C, we starting from A and try to find a path to C. Now it is clearly a graph problem. $\frac{A}{B}$$\frac{A}{B}$ represent a directional edge from A to B with its value as the weight, by following this, we can construct a graph with the equations array and the value array.

For each query, we can start from the first node and take the second node as the target to do a DFS algorithm to find if there exists a path.

DFS approach

​x
class Solution {
    double dfs(unordered_map<string, unordered_map<string, double>>& adjacent, string curr, double val, const string& target, unordered_set<string>& visited) {
        if(adjacent[curr].count(target) != 0) return val * adjacent[curr][target];
        if(visited.count(curr)) return -1.0;
        
        visited.insert(curr);
        for(auto& iter : adjacent[curr]) {
            double ret = dfs(adjacent, iter.first, val * iter.second, target, visited);
            if(ret != -1.0) return ret;
        }
        visited.erase(curr);

        return -1.0;
    }
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        int m = equations.size(), n = queries.size();
        unordered_map<string, unordered_map<string, double>> adjacent;
        for(int i=0; i<m; ++i) {
            adjacent[equations[i][0]][equations[i][1]] = values[i];
            adjacent[equations[i][1]][equations[i][0]] = 1.0 / values[i];
            adjacent[equations[i][0]][equations[i][0]] = 1.0;
            adjacent[equations[i][1]][equations[i][1]] = 1.0;
        }

        unordered_set<string> visited;

        vector<double> ans;
        ans.reserve(n);
        for(int i=0; i<n; ++i) {
            visited.clear();
            ans.push_back(dfs(adjacent, queries[i][0], 1.0, queries[i][1], visited));
        }

        return ans;
    }
};

It's like a standard procedure to the DFS. We need to setup a visited container to avoid repeat. Putting all the values that we need at each round in the parameter field. And by the way, don't forget the $\frac{A}{A}$$\frac{A}{A}$ always equals to one, we could add this when construction the adjacent array (i.e. the graph relationship).

The Union Find approach

It is an interesting perspective to see this problem. Finding the path ideology can also be applied to the Union Find. But I find it a bit complex and un-intuitive. Here is the LeetCode Official Editorial for your reference.

What I learned

The ability of abstraction is important when dealing with problems in maths, computer science and more. This problem gives us a glimpse of how we can abstract a problem to what we comfort with. The division relationship to the graph node pattern. It is worth to take 10 more minutes to think about the ideology behind it.