grid47 Exploring patterns and algorithms
Sep 28, 2024
7 min read
Solution to LeetCode 399: Evaluate Division Problem
You are given a list of equations and their corresponding values, where each equation represents a division between two variables. Your task is to determine the result of several queries asking for the division result of two given variables.
Problem
Approach
Steps
Complexity
Input: You are given two lists: `equations` representing division relations and `values` representing the results of those divisions. You are also given a list of `queries` that you need to evaluate.
• Each equation contains two strings with lengths from 1 to 5.
Output: For each query, return the result of the division if it can be determined, otherwise return -1.0.
Example: Output: [6.0, 0.5, -1.0, 1.0, -1.0]
Constraints:
• The division is guaranteed to be valid for each equation.
• Queries asking for divisions between undefined variables must return -1.0.
Goal: Use depth-first search (DFS) to explore possible paths in the graph and compute the result of each query.
Steps:
• Construct a graph where each variable is a node, and each equation provides an edge with a weight representing the division result.
• For each query, use DFS to explore the graph from the starting node (variable) to the target node and compute the division result along the path.
Goal: Ensure that there are no contradictions in the input equations and that division by zero does not occur.
Steps:
• The variables in queries must be part of the equations provided.
Assumptions:
• All equations are valid and there are no contradictions.
• Evaluating queries will not result in division by zero.
• Input: For the equations [['a', 'b'], ['b', 'c']] and values [2.0, 3.0], the query ['a', 'c'] will return 6.0 because a / b = 2 and b / c = 3, so a / c = 2 * 3 = 6.
• Explanation: We first find the direct relations between variables and then use those relations to compute the result for each query.
Approach: The problem can be approached by constructing a graph from the equations, where each node represents a variable, and each edge represents a division relation. DFS is then used to traverse the graph to find answers to the queries.
Observations:
• Equations form a graph structure, with variables as nodes and division results as edge weights.
• We need to perform DFS to explore possible paths and compute the result for each query.
Steps:
• 1. Build a graph of variables with their corresponding division results.
• 2. For each query, perform DFS to compute the result, keeping track of visited nodes to avoid cycles.
Empty Inputs:
• Queries for undefined variables should return -1.0.
Large Inputs:
• Handle large numbers of equations and queries efficiently.
Special Values:
• Return -1.0 for queries involving variables that do not appear in the equations.
Constraints:
• Queries involving variables not present in the equations are invalid and should return -1.0.
vector<double> calcEquation(vector<vector<string>>& eqn, vector<double>& val, vector<vector<string>>& q) {
map<string, vector<pair<string, double>>> graph;
for(int i =0; i < eqn.size(); i++) {
double w = val[i];
graph[eqn[i][0]].push_back(make_pair(eqn[i][1], w));
if (w ==0) continue;
graph[eqn[i][1]].push_back(make_pair(eqn[i][0], 1/ w));
}
vector<double> ans;
for(int i =0; i < q.size(); i++) {
set<string> vis;
double res = dfs(q[i][0], q[i][1], vis, graph);
if(res <0) res =-1;
ans.push_back(res);
}
return ans;
}
doubledfs(string start, string end, set<string>&vis, map<string, vector<pair<string, double>>>&gph) {
if(start == end) return gph.count(start)?1:-1;
vis.insert(start);
double ans =-1;
for(pair<string, double>x: gph[start]) {
if(vis.count(x.first)) continue;
double res = x.second * dfs(x.first, end, vis, gph);
if(res <0) continue;
return res;
}
return ans;
}
Define the main function `calcEquation` that takes the list of equations (`eqn`), their corresponding values (`val`), and queries (`q`) as input.
2 : Graph Representation
map<string, vector<pair<string, double>>> graph;
Create a graph to represent the equations where each node is a string (variable) and each edge is a pair (connected variable and the corresponding value).
3 : Graph Construction
for(int i =0; i < eqn.size(); i++) {
Loop through the list of equations to build the graph with the given relationships between variables.
4 : Graph Construction
double w = val[i];
Extract the weight (value) associated with the current equation.
