题目链接:https://leetcode-cn.com/problems/satisfiability-of-equality-equations/
题目描述
分析
1. 链表+数组
a. 遍历所有 == 的字符串，将逻辑相等的字符添加到链表中; b. 遍历 != 字符串，若两个字符都在一个链表中，则不成立，返回false
代码实现
public enum Q990 {
instance;
public boolean equationsPossible(String[] equations) {
if(equations.length==0) return true;
List<List<Character>> lists = new ArrayList<>();
for (String equation : equations) {
if (equation.contains("==")) {
char leftC = equation.charAt(0);
char rightC = equation.charAt(3);
List<Character> l1=null;
List<Character> l2=null;
for(List<Character> e:lists){
if(!e.isEmpty()){
// 找到对应的链表
if(e.contains(leftC)){
l1=e;
}
if(e.contains(rightC)){
l2=e;
}
}
}
// 如果 l=r 则两个数组相等，合并链表
if(l1!=null&&l2!=null&&l1!=l2){
l1.addAll(l2);
l2.clear();
// 都为空，则添加链表
}else if(l1==null&&l2==null){
List<Character> linkedList=new LinkedList<>();
linkedList.add(leftC);
if(leftC!=rightC){
linkedList.add(rightC);
}
lists.add(linkedList);
// 若有一个为空，则字符添加到链表中
}else if(l1!=null&&l2==null){
l1.add(rightC);
}else if(l1==null&&l2!=null){
l2.add(leftC);
}
}
}
// 对 != 字符校验
for (String equation : equations) {
if (equation.contains("!=")) {
char leftC = equation.charAt(0);
char rightC = equation.charAt(3);
if (leftC == rightC) return false;
for (List<Character> list : lists) {
if (!list.isEmpty()) {
// 若左右字符都在一个链表中，则false
if (list.contains(leftC) && list.contains(rightC)) {
return false;
}
}
}
}
}
return true;
}
public static void main(String[] args) {
// assert false
System.out.println(Q990.instance.equationsPossible(new String[]{"f==a","a==b","f!=e","a==c","b==e","c==f"}));
// assert false
System.out.println(Q990.instance.equationsPossible(new String[]{"d!=b","b==b","d==a","e!=b","f!=f","c==a"}));
// assert false
System.out.println(Q990.instance.equationsPossible(new String[]{"a==b","c==d","a==c","a!=d"}));
// assert false
System.out.println(Q990.instance.equationsPossible(new String[]{"a==b","e==c","b==c","a!=e"}));
// assert true
System.out.println(Q990.instance.equationsPossible(new String[]{"e==e","d!=e","c==d","d!=e"}));
// assert false
System.out.println(Q990.instance.equationsPossible(new String[]{"e!=c","b!=b","b!=a","e==d"}));
// assert true
System.out.println(Q990.instance.equationsPossible(new String[]{"b==b","b==e","e==c","d!=e"}));
// assert false
System.out.println(Q990.instance.equationsPossible(new String[]{"a!=a"}));
// assert false
System.out.println(Q990.instance.equationsPossible(new String[]{"a==b","b!=c","c==a"}));
// assert true
System.out.println(Q990.instance.equationsPossible(new String[]{"a==b","b==c","a==c"}));
// assert true
System.out.println(Q990.instance.equationsPossible(new String[]{"c==c","b==d","x!=z"}));
// assert true
System.out.println(Q990.instance.equationsPossible(new String[]{"a==b","b==c","f==e","a==e","e==c"}));
// assert true
System.out.println(Q990.instance.equationsPossible(new String[]{"a==a","b==b","c==c","d==d","e==e"}));
// assert true
System.out.println(Q990.instance.equationsPossible(new String[]{"a!=b","c==c"}));
// assert true
System.out.println(Q990.instance.equationsPossible(new String[]{"a==b","b==a"}));
}
}
