等式方程的可满足性

标签: 并查集 图 数组 字符串

难度: Medium

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 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

提示：

  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] 是 '='

Submission

运行时间: 23 ms

内存: 16.1 MB

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        parent = list(range(26))

        # Union phase: process all equations that are equalities to unify groups
        for eq in equations:
            if eq[1] == '=':
                # Extract the variables from the equation and convert to numeric indices
                index1 = ord(eq[0]) - ord('a')
                index2 = ord(eq[3]) - ord('a')
                # Unify the groups by assigning the same root parent
                parent[find(index1)] = find(index2)

        # Check phase: process all equations that are inequalities to detect conflicts
        for eq in equations:
            if eq[1] == '!':
                # Extract the variables from the equation and convert to numeric indices
                index1 = ord(eq[0]) - ord('a')
                index2 = ord(eq[3]) - ord('a')
 
                if find(index1) == find(index2):
                    return False

        return True

Explain

该题解采用了并查集的数据结构来处理等式方程的可满足性问题。首先，初始化一个大小为26的并查集，代表26个字母。然后，遍历所有等式，如果是相等关系（'=='），则将两个变量合并到同一个集合中。在合并的过程中，使用路径压缩优化，以加快查找根节点的速度。最后，再次遍历所有等式，如果是不等关系（'!='），则检查两个变量是否在同一个集合中，如果是，则表示无法满足所有给定的方程，返回false。如果所有不等关系都没有矛盾，则返回true。

时间复杂度: O(N)

空间复杂度: O(1)

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        parent = list(range(26))

        # Union phase: process all equations that are equalities to unify groups
        for eq in equations:
            if eq[1] == '=':
                index1 = ord(eq[0]) - ord('a')
                index2 = ord(eq[3]) - ord('a')
                parent[find(index1)] = find(index2)

        # Check phase: process all equations that are inequalities to detect conflicts
        for eq in equations:
            if eq[1] == '!':
                index1 = ord(eq[0]) - ord('a')
                index2 = ord(eq[3]) - ord('a')
                if find(index1) == find(index2):
                    return False

        return True

Explore

在并查集中，路径压缩的目的是在执行查找操作时优化树的形状，使得任何节点到其根节点的路径尽可能短。在路径压缩过程中，我们递归地找到一个节点的根节点，并在途中的每一个节点直接连接到根节点。这样，下次查找同一个节点时，或者查找同一路径上的其他节点时，都能更快地到达根节点。尽管路径压缩可能暂时使一些节点不直接指向根节点，但是在连续的find操作中，所有访问过的节点最终都会直接指向根节点，从而确保了结构的最优化。

在处理不等式'!='时，如果两个变量已经在一个集合中，意味着根据之前的等式'=='，这两个变量已经被认定为相等。然而，不等式'!='要求这两个变量不相等，这与之前的推断相冲突。因此，如果在处理不等式时发现两个变量在同一个集合中，就意味着无法同时满足'=='和'!='的要求，从而可以立即判断整个方程组是不满足的，并返回false。

题解中选择将一个变量的根节点直接设置为另一个变量的根节点是一种简化的合并方式，这种方法易于实现且在许多情况下效率较高。尽管按秩合并（或称按大小合并）可以进一步优化并查集的性能，通过保持树的高度尽可能低来减少查找路径的长度，但在具体问题中，如等式方程的可满足性问题，简单的路径压缩已经足够处理大多数情况。如果需要处理的数据量极大或者查询非常频繁，可以考虑使用按秩合并来优化性能。

如果等式数组中只包含'!='关系，该算法仍然有效且不需要调整。在这种情况下，由于没有'=='关系，所有的变量默认不在同一个集合中。因此，在处理'!='关系时，只要检查两个变量是否意外地在同一个集合中，如果不在，就继续处理下一个不等式。由于没有等式来合并任何变量，这种情况下的算法简单地遍历所有不等式，检查是否有矛盾存在。如果没有发现任何矛盾，则返回true，否则返回false。