原题
给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。
示例 1:
输入： ["ab","b!=a"] 输出： false
解释： 如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。
示例 2:
输入： ["ba","ab"] 输出： true
说明： 我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。
示例 3：
输入： ["ab","bc","ac"] 输出： true
示例 4：
输入： ["ab","b!=c","ca"] 输出： false
示例 5：
输入： ["cc","bd","x!=z"] 输出： true
提示：
1 <= equations.length <= 500equations[i].length == 4equations[i][0]和equations[i][3]是小写字母equations[i][1]要么是'='，要么是'!'equations[i][2]是'='
解法
本题解同步发于leetcode题解：简洁的Java并查集
思想
见代码部分
代码
我写的这个代码没有任何优化但是很简洁，使用的HashMap实现的并查集（如果不了解并查集建议先去学习一下哦，还是蛮实用的一个数据结构的）
比较重要的思路是一定要先将字符串方程按相等到不等来排序，相等的方程用于建立并查集，不等的方程用于判断是否出错（即不等的两个代数是否出现在了同一个集合中）。
class Solution {
public boolean equationsPossible(String[] equations) {
// 并查集
Map<Character,Character> father = new HashMap<>();
// 先将字符串方程从相等到不等排序
Arrays.sort(equations,(s1,s2)->{
if(s1.charAt(1)==s2.charAt(1)) return 0;
return s1.charAt(1)=='='?-1:1;
});
for(String s:equations){
char[] chars = s.toCharArray();
char first = chars[0];
char second = chars[3];
// 获取根代表
while(father.containsKey(first) ) first = father.get(first);
while(father.containsKey(second)) second = father.get(second);
// 如果是不等，但根代表相同，说明出错
if(chars[1] == '!'){
if(first == second) return false;
// 如果是相等，跳过根代表相同的情况，把一个根代表连接到另一个根代表上（合并集合）
}else{
if(first == second) continue;
father.put(first, second);
}
}
return true;
}
}
刚看了下官方的题解并没有先排序，而是进行了两次遍历，第一次处理相等的，第二次处理不等的，确实比我写的时间复杂度要好，那么按这个思路修改之后就是：
class Solution {
public boolean equationsPossible(String[] equations) {
Map<Character,Character> father = new HashMap<>();
//建立并查集
for(String s:equations){
char[] chars = s.toCharArray();
if(chars[1] == '='){
char first = chars[0];
char second = chars[3];
while(father.containsKey(first) ) first = father.get(first);
while(father.containsKey(second)) second = father.get(second);
if(first == second) continue;
father.put(first, second);
}
}
//检查是否有错
for(String s:equations){
char[] chars = s.toCharArray();
if(chars[1] == '!'){
char first = chars[0];
char second = chars[3];
while(father.containsKey(first) ) first = father.get(first);
while(father.containsKey(second)) second = father.get(second);
if(first == second) return false;
}
}
return true;
}
}
可以发现有一些重复代码，如果抽取成一个函数会更简洁，还有哈希集可以写成数组，时间成本会更低一些，感兴趣的小伙伴自己试试优化啦(^_^)。
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode990-%e7%ad%89%e5%bc%8f%e6%96%b9%e7%a8%8b%e7%9a%84%e5%8f%af%e6%bb%a1%e8%b6%b3%e6%80%a7/
