leetcode990-等式方程的可满足性

原题

给定一个由表示变量之间关系的字符串方程组成的数组,每个字符串方程 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. 1 <= equations.length <= 500
  2. equations[i].length == 4
  3. equations[i][0] 和 equations[i][3] 是小写字母
  4. equations[i][1] 要么是 '=',要么是 '!'
  5. 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/