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 \times \log n)$ or $O(n \times \alpha(n))$, and the space complexity is $O(n)$. Here, $n$ is the number of equations.
Similar problems:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| 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];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| 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;
}
|
