990. 等式方程的可满足性
给定一个由表示变量之间关系的字符串方程组成的数组,每个字符串方程 equations[i] 的长度为 4,并采用两种不同的形式之一:"a==b" 或 "a!=b"。在这里,a 和 b 是小写字母(不一定不同),表示单字母变量名。
只有当可以将整数分配给变量名,以便满足所有给定的方程时才返回 true,否则返回 false。
示例 1:
输入:["a==b","b!=a"]
输出:false
解释:如果我们指定,a = 1 且 b = 1,那么可以满足第一个方程,但无法满足第二个方程。没有办法分配变量同时满足这两个方程。
示例 2:
输入:["b==a","a==b"]
输出:true
解释:我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。
示例 3:
输入:["a==b","b==c","a==c"]
输出:true
示例 4:
输入:["a==b","b!=c","c==a"]
输出:false
示例 5:
输入:["c==c","b==d","x!=z"]
输出:true
运行结果
解题思路
利用并查集:初始化26个小写字母
遍历相等的情况:则让等式两方合并
遍历不等的情况:不与相等的情况冲突
java代码
class Solution { public boolean equationsPossible(String[] equations) { if(equations.length == 0) return true; UF uf=new UF(26); for(String equation:equations){ if(equation.charAt(1)=='='){ char x=equation.charAt(0); char y=equation.charAt(3); uf.union(x-'a',y-'a'); } } for(String equation:equations){ if(equation.charAt(1)=='!'){ char x=equation.charAt(0); char y=equation.charAt(3); if(uf.connected(x-'a',y-'a')){ return false; } } } return true; } class UF{ private int[] parent; private int[] size; private int count; public UF(int n){ parent=new int[n]; size=new int[n]; count=n; for(int i=0;i<n;i++){ parent[i]=i; size[i]=1; count=n; } } public void union(int a,int b){ int roota=find(a); int rootb=find(b); if(roota == rootb) return; if(size[roota]>size[rootb]){ parent[rootb]=roota; size[roota]+=size[rootb]; count--; } else{ parent[roota]=rootb; size[rootb]+=size[roota]; count--; } } public int find(int x){ while(parent[x] != x){ parent[x]=parent[parent[x]]; x=parent[x]; } return x; } public boolean connected(int a,int b){ int roota=find(a); int rootb=find(b); return roota == rootb; } public int count(){ return count; } } }