LeetCode 990. 等式方程的可满足性

约 5 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节
标签
数组 字符串 图 并查集

题目描述

✅ 990. 等式方程的可满足性

image-20260928225443572

image-20260928225443573

题意分析

每个方程表示两个小写字母变量相等或不相等，判断能否给所有变量赋整数值，使全部方程同时成立。相等关系具有传递性，因此不能只逐条检查直接出现的相反方程。

解法：并查集合并连通块

核心思路

[!blue]

相等方程把变量连接成若干组，同一组中的变量都被强制取相同值。并查集保存这种分组：parent 记录父节点，find(x) 沿父链接找到根，根相同就属于同一组。合并两个等式端点时，连接的是它们所在集合的根，整组变量随之合并。

先处理全部 ==，让直接或间接的相等关系都体现到最终分组中。再处理 !=：若两端同根，等式要求它们相等，而当前不等式要求不同，必然矛盾，可以立即返回 false。

如果所有不等式都连接不同集合，就给每个集合分配一个不同整数。同组变量满足全部等式，异组变量满足所有不等式，因此这样的赋值一定存在，返回 true。这也说明只需要记录等式分组，不需要再对不等关系做合并或传递。

查根时顺便缩短父链接，只会让节点更快到达原来的根，不改变它所属的集合。

解题步骤

  • 为 26 个字母建立独立集合，令 parent[i] = i。
  • 第一遍只处理等式，读取两端变量并合并它们的根。
  • 第二遍只处理不等式，若两个变量的根相同，立即返回 false。
  • 全部检查通过则返回 true。自相等无需额外操作，自不等会被同根判断直接排除。

代码实现

class Solution {
    public boolean equationsPossible(String[] equations) {
        int[] parent = new int[26];

        for (int i = 0; i < 26; i++) {
            parent[i] = i;
        }

        for (String eq : equations) {
            // 先把全部相等约束合并，再统一验证不等式。
            if (eq.charAt(1) == '=') {
                int a = eq.charAt(0) - 'a';
                int b = eq.charAt(3) - 'a';

                union(parent, a, b);
            }
        }

        for (String eq : equations) {
            // 此时分组已经确定，同根的不等式就是矛盾。
            if (eq.charAt(1) == '!') {
                int a = eq.charAt(0) - 'a';
                int b = eq.charAt(3) - 'a';

                if (find(parent, a) == find(parent, b)) {
                    return false;
                }
            }
        }

        return true;
    }

    private int find(int[] parent, int x) {
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]);
        }

        return parent[x];
    }

    private void union(int[] parent, int a, int b) {
        int pa = find(parent, a);
        int pb = find(parent, b);

        if (pa != pb) {
            // 连接两棵树的根，才能合并完整集合。
            parent[pa] = pb;
        }
    }
}

func equationsPossible(equations []string) bool {
    parent := make([]int, 26)
    for i := 0; i < 26; i++ {
        parent[i] = i
    }

    find := func(x int) int {
        for parent[x] != x {
            parent[x] = parent[parent[x]]
            x = parent[x]
        }
        return x
    }

    union := func(a int, b int) {
        pa := find(a)
        pb := find(b)
        if pa != pb {
            // 连接两棵树的根，才能合并完整集合。
            parent[pa] = pb
        }
    }

    for _, eq := range equations {
        // 先把全部相等约束合并，再统一验证不等式。
        if eq[1] == '=' {
            a := int(eq[0] - 'a')
            b := int(eq[3] - 'a')
            union(a, b)
        }
    }

    for _, eq := range equations {
        // 此时分组已经确定，同根的不等式就是矛盾。
        if eq[1] == '!' {
            a := int(eq[0] - 'a')
            b := int(eq[3] - 'a')
            if find(a) == find(b) {
                return false
            }
        }
    }

    return true
}

复杂度分析

设方程数量为 n。

  • 时间复杂度：$O(n)$。变量固定只有 26 个，即使沿整条父链查根，长度也受常数限制；两遍扫描均为线性时间。
  • 空间复杂度：$O(1)$。并查集数组长度固定为 26，Java 查根递归深度也受此限制。

关键点总结

[!green]

  • 并查集记录哪些变量被强制相等，不需要计算它们具体取什么值。
  • 必须等所有等式处理完，再用最终分组验证不等式。
  • 同根不等式给出矛盾；不存在这种矛盾时，给各组不同整数便能构造可行赋值。

易错点总结

[!yellow]

  • 一边合并一边检查不等式，会漏掉后续等式才建立的相等关系。
  • 不等关系没有相同的传递规则，不能用它合并集合。
  • 比较两端当前的 parent 值不一定能判断同组，必须查到各自的根。
  • 操作符的后一个字符都是 =，区分等式和不等式要读取下标 1。

相似题目

题目 难度 关联与区别
721. 账户合并 中等 先把相等关系合并成等价类，本题还要检查每条不等关系是否落入同一分量。
LCR 111. 除法求值 中等 两题都合并变量所在的并查集分量；本题只保存等价关系，该题在父指针上增加比率并在路径压缩时同步更新权重。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/71512261
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！