提示：
1 <= equations.length <= 500
equations[i].length == 4
equations[i] [0] 和 equations[i][3] 是小写字母
equations[i] [1] 要么是 '='，要么是 '!'
equations[i] [2] 是 '='
题解1
思路
- 方程只有
==和!=两种情况，第一次遍历equations，当方程为==时，用长度为26（只有小写字母）的数组实时更新各字母的权值。 - 第二次遍历
equations，判定方程为!=时，逻辑是否矛盾，矛盾有以下两种情形：- 等式左右两边字母相同
- 等式左右两边权值都不为0且相同
代码
//直观方法 1ms
public static boolean equationsPossible2(String[] equations) {
int[] arr = new int[26];
int count = 1;
for (String str : equations) {
if (str.charAt(1) == '=') {
int start = str.charAt(0) - 'a';
int end = str.charAt(3) - 'a';
if (arr[start] == 0 && arr[end] == 0) {
//都没出现过
arr[start] = arr[end] = count++;
} else if (arr[start] == 0 || arr[end] == 0) {
//只有一个出现个，则把权值设置一样
int max = Math.max(arr[start], arr[end]);
arr[start] = arr[end] = max;
} else {
//都出现过，两个集合相交， 把所有等于他俩值的权值设置同一个值。
int v1 = arr[start];
int v2 = arr[end];
for (int i = 0; i < arr.length; i++) {
if (arr[i] == v1 || arr[i] == v2) {
arr[i] = v1;
}
}
}
}
}
for (String s : equations) {
if (s.charAt(1) == '!') {
int start = s.charAt(0) - 'a';
int end = s.charAt(3) - 'a';
if (start == end) {//同一个字母
return false;
}
if (arr[start] != 0 && arr[end] != 0) {
if (arr[start] == arr[end]) {
return false;//矛盾
}
}
}
}
return true;
}
并查集
思路
代码
//1ms
public boolean equationsPossible(String[] equations) {
int len = equations.length;
int[] parent = new int[26];
for (int i = 0; i < 26; i++) {
parent[i] = i;
}
for (String str : equations) {
if (str.charAt(1) == '=') {
int index1 = str.charAt(0) - 'a';
int index2 = str.charAt(3) - 'a';
union(parent, index1, index2);
}
}
for (String str : equations) {
if (str.charAt(1) == '!') {
int index1 = str.charAt(0) - 'a';
int index2 = str.charAt(3) - 'a';
if (find(parent, index1) == find(parent, index2)) {
return false;
}
}
}
return true;
}
private void union(int[] parent, int index1, int index2) {
parent[find(parent, index1)] = find(parent, index2);
}
private int find(int[] parent, int index) {
while (parent[index] != index) {
parent[index] = parent[parent[index]];
index = parent[index];
}
return index;
}
}
参考链接