Algorithm
Problem Name: 399. 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.
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 ]
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 <= 20equations[i].length == 21 <= Ai.length, Bi.length <= 5values.length == equations.length0.0 < values[i] <= 20.01 <= queries.length <= 20queries[i].length == 21 <= Cj.length, Dj.length <= 5Ai, Bi, Cj, Djconsist of lower case English letters and digits.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#define DUMP(OP, OP1, OP2) do { } while (0)
double math(int k, double op1, double op2) {
DUMP(k, op1, op2);
switch(k) {
case 1:
op1 = 1.0;
break;
case 2:
op1 = op2;
break;
case 3:
op1 = 1 / op2;
break;
case 4:
case 5:
op1 = op1 * op2;
break;
case 6:
case 7:
op1 = op1 / op2;
break;
}
return op1;
}
int match(char **strs, char *fm, char *fz) {
int x00, x01, x10, x11;
int k = 0;
x00 = !strcmp(fm, strs[0]);
x01 = !strcmp(fm, strs[1]);
x10 = !strcmp(fz, strs[0]);
x11 = !strcmp(fz, strs[1]);
if ((!x00 && !x01 && !x10 && !x11) ||
(x00 && x01 && !x10) ||
(x10 && x11 && !x00)){
k = 0; // no match or useless match
} else if ((x00 && x10) || (x01 && x11)) {
k = 1; // 1
} else if (x00 && x11) {
k = 2; // equal
} else if (x01 && x10) {
k = 3; // reverse
} else if (x00) {
k = 4; // multiply
} else if (x11) {
k = 5;
} else if (x01) {
k = 6; // divide
} else if (x10) {
k = 7;
}
return k;
}
int calc(int *visited, double *d, char ***equa, double *val, int rowsz, char *fm, char *fz) {
int i, k, x;
for (i = 0; i < rowsz; i ++) {
if (visited[i] == 0) {
k = match(equa[i], fm, fz);
if (k >= 1 && k < = 3) {
*d = math(k, *d, val[i]);
return 1;
} else if (k != 0) {
visited[i] = 1;
if (k == 4) {
x = calc(visited, d, equa, val, rowsz, equa[i][1], fz);
} else if (k == 5) {
x = calc(visited, d, equa, val, rowsz, fm, equa[i][0]);
} else if (k == 6) {
x = calc(visited, d, equa, val, rowsz, equa[i][0], fz);
} else /*if (k == 7)*/ {
x = calc(visited, d, equa, val, rowsz, fm, equa[i][1]);
}
visited[i] = 0;
if (x) {
*d = math(k, *d, val[i]);
return 1;
}
}
}
}
return 0;
}
double* calcEquation(char*** equations, int equationsRowSize, int equationsColSize, double* values, int valuesSize, char*** queries, int queriesRowSize, int queriesColSize, int* returnSize) {
int *visited;
double *results, d;
int i;
results = malloc(queriesRowSize * sizeof(double));
visited = calloc(equationsRowSize, sizeof(int));
//assert(result && visited);
*returnSize = queriesRowSize;
for (i = 0; i < queriesRowSize; i ++) {
d = -1.0;
calc(visited, &d, equations, values, equationsRowSize, queries[i][0], queries[i][1]);
results[i] = d;
}
free(visited);
return results;
}
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]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
private:
unordered_map calcEquation(vector<pair& values, vector<pairres;
for(int i = 0; i < values.size(); i++){
auto p = equations[i];
weight[p.first][p.second] = values[i];
weight[p.second][p.first] = 1 / values[i];
graph[p.first].push_back(p.second);
graph[p.second].push_back(p.first);
}
for(int i = 0; i < queries.size(); i++){
unordered_setvisited;
deque < pair calcEquation(vector<pair& values, vector<pairres;
unordered_mapvisited;
queue<pair 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]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public double[] calcEquation(List();
Map valueMap = new HashMap<>();
for (int i = 0; i < equations.size(); i++) {
String equation = equations.get(i).get(0) + "/" + equations.get(i).get(1);
connectionMap.computeIfAbsent(equations.get(i).get(0), k -> new HashSet < >())
.add(equations.get(i).get(1));
connectionMap.computeIfAbsent(equations.get(i).get(1), k -> new HashSet<>())
.add(equations.get(i).get(0));
valueMap.put(equation, values[i]);
}
for (int i = 0; i < queries.size(); i++) {
String source = queries.get(i).get(0);
String target = queries.get(i).get(1);
double[] res = {-1.0};
dfs(connectionMap, valueMap, source, target, new HashSet < >(), res, 1.0);
ans[i] = res[0];
}
return ans;
}
private void dfs(Map < String, Set valueMap,
String source, String target, Set visited, double[] res, double currVal) {
if (source.equals(target) && (
connectionMap.containsKey(source) || connectionMap.containsKey(target))
) {
res[0] = currVal;
return;
}
for (String connection : connectionMap.getOrDefault(source, new HashSet < >())) {
if (!visited.contains(connection)) {
visited.add(connection);
double newwCurrVal = currVal * (
valueMap.containsKey(source + "/" + connection) ?
valueMap.get(source + "/" + connection) :
(1 / valueMap.get(connection + "/" + source))
);
dfs(connectionMap, valueMap, connection, target, visited, res, newwCurrVal);
}
}
}
}
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]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const calcEquation = function(equations, values, queries) {
const m = {};
for (let i = 0; i < values.length; i++) {
if (!m.hasOwnProperty(equations[i][0])) m[equations[i][0]] = {};
if (!m.hasOwnProperty(equations[i][1])) m[equations[i][1]] = {};
m[equations[i][0]][equations[i][1]] = values[i];
m[equations[i][1]][equations[i][0]] = 1 / values[i];
}
const r = [];
for (let i = 0; i < queries.length; i++) {
r[i] = dfs(queries[i][0], queries[i][1], 1, m, []);
}
return r;
};
function dfs(s, t, r, m, seen) {
if (!m.hasOwnProperty(s) || !hsetAdd(seen, s)) return -1;
if (s === t) return r;
let next = m[s];
for (let c of Object.keys(next)) {
let result = dfs(c, t, r * next[c], m, seen);
if (result !== -1) return result;
}
return -1;
}
function hsetAdd(arr, el) {
if (arr.indexOf(el) === -1) {
arr.push(el);
return true;
} else {
return false;
}
}
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]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def calcEquation(self, equations, values, queries):
def explore(x, y, r, q):
results[(x, y)] = r
for z in edges[y]:
if z not in q:
results[(x, z)], results[(z, x)] = r * vals[(y, z)], 1 / (r * vals[(y, z)])
explore(x, z, r * vals[(y, z)], q | {z})
edges, vals, visited, results, res = collections.defaultdict(set), {}, set(), {}, []
for i, eq in enumerate(equations):
edges[eq[0]].add(eq[1])
edges[eq[1]].add(eq[0])
vals[(eq[0], eq[1])], vals[(eq[1], eq[0])] = values[i], 1 / values[i]
for i, eq in enumerate(equations):
for p in eq:
if p not in visited:
visited.add(p)
explore(p, p, 1.0, {p})
for q in queries:
if (q[0], q[1]) in results: res += results[(q[0], q[1])],
else: res += -1.0,
return res
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]
#6 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0399_EvaluateDivision
{
public double[] CalcEquation(IList < IList parents = new Dictionary();
public Node Find(string index)
{
if (!parents.ContainsKey(index))
parents.Add(index, new Node(index, 1.0));
else if (parents[index].ParentIndex != index)
{
var value = parents[index].Value;
var parent = Find(parents[index].ParentIndex);
parents[index] = new Node(parent.ParentIndex, value * parent.Value);
}
return parents[index];
}
public bool Exist(string index)
{
return parents.ContainsKey(index);
}
public void Union(string index1, string index2, double value)
{
var pIndex1 = Find(index1);
var pIndex2 = Find(index2);
if (pIndex1.ParentIndex != pIndex2.ParentIndex)
parents[pIndex1.ParentIndex] = new Node(pIndex2.ParentIndex, value * pIndex2.Value / pIndex1.Value);
}
}
public class Node
{
public Node(string parentIndex, double value)
{
ParentIndex = parentIndex;
Value = value;
}
public string ParentIndex { get; set; }
public double Value { get; set; }
}
}
}
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]