Description
You are given a 2D array of strings equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] means that Ai / Bi = values[i].
Determine if there exists a contradiction in the equations. Return true if there is a contradiction, or false otherwise.
Note:
- When checking if two numbers are equal, check that their absolute difference is less than
10-5.
- The testcases are generated such that there are no cases targeting precision, i.e. using
double is enough to solve the problem.
Example 1:
Input: equations = [["a","b"],["b","c"],["a","c"]], values = [3,0.5,1.5]
Output: false
Explanation:
The given equations are: a / b = 3, b / c = 0.5, a / c = 1.5
There are no contradictions in the equations. One possible assignment to satisfy all equations is:
a = 3, b = 1 and c = 2.
Example 2:
Input: equations = [["le","et"],["le","code"],["code","et"]], values = [2,5,0.5]
Output: true
Explanation:
The given equations are: le / et = 2, le / code = 5, code / et = 0.5
Based on the first two equations, we get code / et = 0.4.
Since the third equation is code / et = 0.5, we get a contradiction.
Constraints:
1 <= equations.length <= 100equations[i].length == 21 <= Ai.length, Bi.length <= 5Ai, Bi consist of lowercase English letters.equations.length == values.length0.0 < values[i] <= 10.0values[i] has a maximum of 2 decimal places.
Solutions
Solution 1: Weighted Union-Find
First, we convert the strings into integers starting from 0. Then, we traverse all the equations, map the two strings in each equation to the corresponding integers a and b. If these two integers are not in the same set, we merge them into the same set and record the weights of the two integers, which is the ratio of a to b. If these two integers are in the same set, we check whether their weights satisfy the equation. If not, we return true.
The time complexity is O(n × log n) or O(n × Î±(n)), and the space complexity is O(n). Here, n is the number of equations.
Similar problems:
PythonJavaC++GoTypeScript
class Solution:
def checkContradictions(
self, equations: List[List[str]], values: List[float]
) -> bool:
def find(x: int) -> int:
if p[x] != x:
root = find(p[x])
w[x] *= w[p[x]]
p[x] = root
return p[x]
d = defaultdict(int)
n = 0
for e in equations:
for s in e:
if s not in d:
d[s] = n
n += 1
p = list(range(n))
w = [1.0] * n
eps = 1e-5
for (a, b), v in zip(equations, values):
a, b = d[a], d[b]
pa, pb = find(a), find(b)
if pa != pb:
p[pb] = pa
w[pb] = v * w[a] / w[b]
elif abs(v * w[a] - w[b]) >= eps:
return True
return False(code-box)
class Solution {
private int[] p;
private double[] w;
public boolean checkContradictions(List<List<String>> equations, double[] values) {
Map<String, Integer> d = new HashMap<>();
int n = 0;
for (var e : equations) {
for (var s : e) {
if (!d.containsKey(s)) {
d.put(s, n++);
}
}
}
p = new int[n];
w = new double[n];
for (int i = 0; i < n; ++i) {
p[i] = i;
w[i] = 1.0;
}
final double eps = 1e-5;
for (int i = 0; i < equations.size(); ++i) {
int a = d.get(equations.get(i).get(0)), b = d.get(equations.get(i).get(1));
int pa = find(a), pb = find(b);
double v = values[i];
if (pa != pb) {
p[pb] = pa;
w[pb] = v * w[a] / w[b];
} else if (Math.abs(v * w[a] - w[b]) >= eps) {
return true;
}
}
return false;
}
private int find(int x) {
if (p[x] != x) {
int root = find(p[x]);
w[x] *= w[p[x]];
p[x] = root;
}
return p[x];
}
}(code-box)
class Solution {
public:
bool checkContradictions(vector<vector<string>>& equations, vector<double>& values) {
unordered_map<string, int> d;
int n = 0;
for (auto& e : equations) {
for (auto& s : e) {
if (!d.count(s)) {
d[s] = n++;
}
}
}
vector<int> p(n);
iota(p.begin(), p.end(), 0);
vector<double> w(n, 1.0);
function<int(int)> find = [&](int x) -> int {
if (p[x] != x) {
int root = find(p[x]);
w[x] *= w[p[x]];
p[x] = root;
}
return p[x];
};
for (int i = 0; i < equations.size(); ++i) {
int a = d[equations[i][0]], b = d[equations[i][1]];
double v = values[i];
int pa = find(a), pb = find(b);
if (pa != pb) {
p[pb] = pa;
w[pb] = v * w[a] / w[b];
} else if (fabs(v * w[a] - w[b]) >= 1e-5) {
return true;
}
}
return false;
}
};(code-box)
func checkContradictions(equations [][]string, values []float64) bool {
d := make(map[string]int)
n := 0
for _, e := range equations {
for _, s := range e {
if _, ok := d[s]; !ok {
d[s] = n
n++
}
}
}
p := make([]int, n)
for i := range p {
p[i] = i
}
w := make([]float64, n)
for i := range w {
w[i] = 1.0
}
var find func(int) int
find = func(x int) int {
if p[x] != x {
root := find(p[x])
w[x] *= w[p[x]]
p[x] = root
}
return p[x]
}
for i, e := range equations {
a, b := d[e[0]], d[e[1]]
v := values[i]
pa, pb := find(a), find(b)
if pa != pb {
p[pb] = pa
w[pb] = v * w[a] / w[b]
} else if v*w[a]-w[b] >= 1e-5 || w[b]-v*w[a] >= 1e-5 {
return true
}
}
return false
}(code-box)
function checkContradictions(equations: string[][], values: number[]): boolean {
const d: { [key: string]: number } = {};
let n = 0;
for (const e of equations) {
for (const s of e) {
if (!(s in d)) {
d[s] = n;
n++;
}
}
}
const p: number[] = Array.from({ length: n }, (_, i) => i);
const w: number[] = Array.from({ length: n }, () => 1.0);
const find = (x: number): number => {
if (p[x] !== x) {
const root = find(p[x]);
w[x] *= w[p[x]];
p[x] = root;
}
return p[x];
};
for (let i = 0; i < equations.length; i++) {
const a = d[equations[i][0]];
const b = d[equations[i][1]];
const v = values[i];
const pa = find(a);
const pb = find(b);
if (pa !== pb) {
p[pb] = pa;
w[pb] = (v * w[a]) / w[b];
} else if (Math.abs(v * w[a] - w[b]) >= 1e-5) {
return true;
}
}
return false;
}(code-box)
