跳至主要內容

0990. 等式方程的可满足性

ITCharge大约 3 分钟

0990. 等式方程的可满足性open in new window

  • 标签:并查集、图、数组、字符串
  • 难度:中等

题目链接

题目大意

描述:给定一个由字符串方程组成的数组 equations,每个字符串方程 equations[i] 的长度为 4,有以下两种形式组成:a==ba!=bab 是小写字母,表示单字母变量名。

要求:判断所有的字符串方程是否能同时满足,如果能同时满足,返回 True,否则返回 False

说明

  • 1equations.length5001 \le equations.length \le 500
  • equations[i].length==4equations[i].length == 4
  • equations[i][0]equations[i][0]equations[i][3]equations[i][3] 是小写字母。
  • equations[i][1]equations[i][1] 要么是 '=',要么是 '!'
  • equations[i][2]'='

示例

  • 示例 1:
输入:["a==b","b!=a"]
输出:False
解释:如果我们指定,a = 1 且 b = 1,那么可以满足第一个方程,但无法满足第二个方程。没有办法分配变量同时满足这两个方程。

解题思路

思路 1:并查集

字符串方程只有 == 或者 !=,可以考虑将相等的遍历划分到相同集合中,然后再遍历所有不等式方程,看方程的两个变量是否在之前划分的相同集合中,如果在则说明不满足。

这就需要用到并查集,具体操作如下:

  • 遍历所有等式方程,将等式两边的单字母变量顶点进行合并。
  • 遍历所有不等式方程,检查不等式两边的单字母遍历是不是在一个连通分量中,如果在则返回 False,否则继续扫描。如果所有不等式检查都没有矛盾,则返回 True

思路 1:并查集代码

class UnionFind:
    def __init__(self, n):                          # 初始化
        self.fa = [i for i in range(n)]             # 每个元素的集合编号初始化为数组 fa 的下标索引
    
    def __find(self, x):                            # 查找元素根节点的集合编号内部实现方法
        while self.fa[x] != x:                      # 递归查找元素的父节点,直到根节点
            self.fa[x] = self.fa[self.fa[x]]        # 隔代压缩优化
            x = self.fa[x]
        return x                                    # 返回元素根节点的集合编号

    def union(self, x, y):                          # 合并操作:令其中一个集合的树根节点指向另一个集合的树根节点
        root_x = self.__find(x)
        root_y = self.__find(y)
        if root_x == root_y:                        # x 和 y 的根节点集合编号相同,说明 x 和 y 已经同属于一个集合
            return False
        
        self.fa[root_x] = root_y                    # x 的根节点连接到 y 的根节点上,成为 y 的根节点的子节点
        return True

    def is_connected(self, x, y):                   # 查询操作:判断 x 和 y 是否同属于一个集合
        return self.__find(x) == self.__find(y)

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        union_find = UnionFind(26)
        for eqation in equations:
            if eqation[1] == "=":
                index1 = ord(eqation[0]) - 97
                index2 = ord(eqation[3]) - 97
                union_find.union(index1, index2)

        for eqation in equations:
            if eqation[1] == "!":
                index1 = ord(eqation[0]) - 97
                index2 = ord(eqation[3]) - 97
                if union_find.is_connected(index1, index2):
                    return False
        return True

思路 1:复杂度分析

  • 时间复杂度O(n+C×logC)O(n + C \times \log C)。其中 nn 是方程组 equationsequations 中的等式数量。CC 是字母变量的数量。本题中变量都是小写字母,即 C26C \le 26
  • 空间复杂度O(C)O(C)