You are given a list of equations in the form A / B = k, where A and B are variables represented as strings, and k is a floating-point number. You are also given a list of queries, where each query is also in the form X / Y. For each query, you are to compute the result of the division based on the given equations. If the answer does not exist, return -1.0.
Constraints:
equations: List of pairs of strings, each representing a division equation.values: List of floating-point numbers, each representing the value of the corresponding equation.queries: List of pairs of strings, each representing a division query.-1.0 for that query.The problem asks us to evaluate division results based on a set of known equations. At first glance, we might consider brute-forcing all possible paths between variables for each query. However, this would be inefficient, especially with many equations and queries.
Instead, we can think of the equations as a graph: each variable is a node, and each equation defines a directed edge with a weight (the division value). For example, A / B = 2.0 means there is an edge from A to B with weight 2.0, and an edge from B to A with weight 0.5. To answer a query like X / Y, we can search for a path from X to Y and multiply the edge weights along the path.
This graph-based approach allows us to efficiently answer queries by traversing the graph, rather than recalculating relationships for each query.
We'll use a graph to represent the relationships between variables. Here's how we'll solve the problem step by step:
A / B = k, add an edge from A to B with weight k, and an edge from B to A with weight 1/k.X / Y, check if both X and Y exist in the graph. If not, return -1.0.X == Y, return 1.0 (since any variable divided by itself is 1).X to find a path to Y. Multiply the weights along the path to compute the division value.This approach is efficient and leverages the structure of the problem by modeling it as a graph traversal problem.
Let's walk through an example:
equations = [["a", "b"], ["b", "c"]]
values = [2.0, 3.0]
queries = [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]
a / b = 2.0 ⇒ a → b (2.0), b → a (0.5)b / c = 3.0 ⇒ b → c (3.0), c → b (1/3.0 = 0.333...)a / c: Path is a → b → c. Value is 2.0 * 3.0 = 6.0.b / a: Path is b → a. Value is 0.5.a / e: e does not exist in the graph. Return -1.0.a / a: Same variable. Return 1.0.x / x: x does not exist. Return -1.0.Brute-force Approach: For each query, searching all possible paths between variables can take exponential time in the worst case (O(N!)), where N is the number of variables. This is highly inefficient.
Optimized (Graph) Approach:
In practice, since the number of variables and equations is usually small, this approach is efficient and scalable.
We approached the Evaluate Division problem by modeling the equations as a weighted, bidirectional graph. By representing variables as nodes and division relationships as weighted edges, we can efficiently answer each query using graph traversal (DFS or BFS). This method is both intuitive and optimal for the problem, leveraging data structures for quick lookups and avoiding redundant calculations. The solution is elegant because it transforms a seemingly complex set of equations into a familiar graph problem, making it easy to reason about and implement.
from collections import defaultdict
class Solution:
def calcEquation(self, equations, values, queries):
graph = defaultdict(dict)
for (a, b), v in zip(equations, values):
graph[a][b] = v
graph[b][a] = 1.0 / v
def dfs(src, dst, visited):
if src not in graph or dst not in graph:
return -1.0
if src == dst:
return 1.0
visited.add(src)
for neighbor, weight in graph[src].items():
if neighbor in visited:
continue
res = dfs(neighbor, dst, visited)
if res != -1.0:
return weight * res
return -1.0
result = []
for x, y in queries:
result.append(dfs(x, y, set()))
return result
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;
class Solution {
public:
double dfs(const string& src, const string& dst,
unordered_map<string, unordered_map<string, double>>& graph,
unordered_set<string>& visited) {
if (graph.find(src) == graph.end() || graph.find(dst) == graph.end())
return -1.0;
if (src == dst)
return 1.0;
visited.insert(src);
for (auto& nb : graph[src]) {
if (visited.count(nb.first)) continue;
double res = dfs(nb.first, dst, graph, visited);
if (res != -1.0)
return nb.second * res;
}
return -1.0;
}
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
unordered_map<string, unordered_map<string, double>> graph;
for (int i = 0; i < equations.size(); ++i) {
string a = equations[i][0], b = equations[i][1];
double v = values[i];
graph[a][b] = v;
graph[b][a] = 1.0 / v;
}
vector<double> result;
for (auto& q : queries) {
unordered_set<string> visited;
result.push_back(dfs(q[0], q[1], graph, visited));
}
return result;
}
};
import java.util.*;
class Solution {
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
Map<String, Map<String, Double>> graph = new HashMap<>();
for (int i = 0; i < equations.size(); i++) {
String a = equations.get(i).get(0), b = equations.get(i).get(1);
double v = values[i];
graph.computeIfAbsent(a, k -> new HashMap<>()).put(b, v);
graph.computeIfAbsent(b, k -> new HashMap<>()).put(a, 1.0 / v);
}
double[] result = new double[queries.size()];
for (int i = 0; i < queries.size(); i++) {
Set<String> visited = new HashSet<>();
result[i] = dfs(queries.get(i).get(0), queries.get(i).get(1), graph, visited);
}
return result;
}
private double dfs(String src, String dst, Map<String, Map<String, Double>> graph, Set<String> visited) {
if (!graph.containsKey(src) || !graph.containsKey(dst))
return -1.0;
if (src.equals(dst))
return 1.0;
visited.add(src);
for (Map.Entry<String, Double> nb : graph.get(src).entrySet()) {
if (visited.contains(nb.getKey()))
continue;
double res = dfs(nb.getKey(), dst, graph, visited);
if (res != -1.0)
return nb.getValue() * res;
}
return -1.0;
}
}
/**
* @param {string[][]} equations
* @param {number[]} values
* @param {string[][]} queries
* @return {number[]}
*/
var calcEquation = function(equations, values, queries) {
const graph = {};
for (let i = 0; i < equations.length; i++) {
const [a, b] = equations[i];
const v = values[i];
if (!graph[a]) graph[a] = {};
if (!graph[b]) graph[b] = {};
graph[a][b] = v;
graph[b][a] = 1 / v;
}
function dfs(src, dst, visited) {
if (!(src in graph) || !(dst in graph)) return -1.0;
if (src === dst) return 1.0;
visited.add(src);
for (const neighbor in graph[src]) {
if (visited.has(neighbor)) continue;
const res = dfs(neighbor, dst, visited);
if (res !== -1.0) return graph[src][neighbor] * res;
}
return -1.0;
}
return queries.map(([x, y]) => dfs(x, y, new Set()));
};