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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| class Solution {
private static class UnionFind {
private int[] parents;
private int[] ranks;
private UnionFind(int size) {
parents = new int[size + 1];
ranks = new int[size + 1];
for (int i = 1; i < size + 1; i++) {
parents[i] = i;
ranks[i] = 1;
}
}
private int find(int node) {
if (parents[node] == node) {
return node;
}
return parents[node] = find(parents[node]);
}
private void union(int nodeOne, int nodeTwo) {
int rootOne = find(nodeOne);
int rootTwo = find(nodeTwo);
if (rootOne != rootTwo) {
if (ranks[rootOne] > ranks[rootTwo]) {
parents[rootTwo] = rootOne;
} else if (ranks[rootOne] < ranks[rootTwo]) {
parents[rootOne] = rootTwo;
} else {
parents[rootTwo] = rootOne;
ranks[rootOne] += 1;
}
}
}
private boolean isConnected(int nodeOne, int nodeTwo) {
return find(nodeOne) == find(nodeTwo);
}
}
public boolean equationsPossible(String[] equations) {
int charCount = 0;
UnionFind uf = new UnionFind(26);
for (String equation : equations) {
if (equation.charAt(1) == '=') {
int firstLetterIdx = equation.charAt(0) - 'a';
int secondLetterIdx = equation.charAt(3) - 'a';
uf.union(firstLetterIdx, secondLetterIdx);
}
}
for (String equation : equations) {
int firstLetterIdx = equation.charAt(0) - 'a';
int secondLetterIdx = equation.charAt(3) - 'a';
if (equation.charAt(1) == '!' && uf.isConnected(firstLetterIdx, secondLetterIdx)) {
return false;
}
}
return true;
}
}
|
union find.
首先把相等的node连接在一起, 然后再遍历一遍看不相等的, 不相等的两个node如果之间被连接起来了, 那么直接返回false.
时间复杂度: O(n) n是equations的个数.
空间复杂度: O(1) 我们需要用到数组存26个nodes.
