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

2021-08-13 HGNULB 约 12 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

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

题意分析

输入是一组长度固定为 4 的字符串，形如 "a==b" 或 "a!=b"，两端是小写字母变量，中间是等号或不等号。问能否给每个变量赋一个整数值，使所有方程同时成立。注意题目不要求给出具体赋值，只要回答可满足性，这意味着我们只需要判断约束之间有没有内在矛盾，而不需要真的去构造解。

关键性质来自「相等」这个关系本身：它是自反、对称、传递的，也就是一个等价关系。一旦 a == b 且 b == c，那么 a == c 就被强制推出，无论是否显式写在输入里。这个传递闭包的特征是最强的算法信号——所有相等约束把变量切分成若干等价类，同一类里的变量必须取同一个值，不同类之间则完全自由。

反过来，不等式 a != b 不具备传递性，它只是对某一对变量提出「不能同类」的否决。由此可以判断：只要不存在「某个不等式的两端落在同一个等价类里」，就一定有解——不同等价类各取一个互不相同的整数即可同时满足全部不等式，而变量最多 26 个，整数取之不尽。所以判定条件是充要的，不存在「局部合法但整体无解」的情况。

规模上变量只有 26 个小写字母，方程数量在数千量级，这个「值域极小而约束很多」的组合提示可以开一个固定长度 26 的数组当容器，不需要任何哈希结构。

边界上要注意："a==a" 这种自反等式永远成立，合并自己到自己是无害的空操作；而 "a!=a" 永远矛盾，必须返回 false——它会被「两端同类」的通用判断自然覆盖，不需要单独写分支。另外方程之间没有顺序含义，"a!=b" 写在 "a==b" 前面还是后面，结果都应该一样。

解法：并查集合并连通块

核心思路

朴素做法是把每个 == 看成一条无向边建图，然后对每个 != 跑一次 DFS/BFS 看两端是否连通。这能过，但每次查询都要重新遍历一遍图，多次查询之间的连通性信息被反复重算，代价是 $O(n^2)$ 量级；而且写起来要建邻接表、开 visited 数组，白板上代码量不小。

瓶颈在于「连通性」被当成一个需要临时计算的问题，而它其实是一个可以增量维护的静态属性。观察到相等关系的传递闭包只会随着等式的加入而变粗（等价类只会合并、永不分裂），说明可以用一种只支持「合并」和「查代表元」的结构一次性把闭包建好，之后每次查询都是常数级。

由此确定算法的不变量：维护一个 parent 数组，任意时刻 find(x) 返回 x 所在等价类的唯一代表元；两个变量当前被已处理的等式强制相等，当且仅当它们的代表元相同。初始时每个字母自成一类，parent[i] = i，对应「没有任何约束时所有变量互不相干」。

还有一个不能忽视的顺序问题：必须先处理完所有等式，再统一检查不等式。如果混在一趟里做，"a!=b" 在前、"a==b" 在后的输入会在检查时看到 a、b 尚未合并，误判为可满足。两趟扫描把「建立闭包」和「验证否决」彻底分开，正是这个算法唯一需要小心的地方。

解题步骤

开长度 26 的 parent 数组并令 parent[i] = i。之所以用数组而不是哈希表，是因为变量域被题目锁死为小写字母，ch - 'a' 就是天然的下标，省掉哈希开销也避免了「变量未出现过要不要先插入」的边界讨论。

第一趟只挑出 eq.charAt(1) == '=' 的方程做合并。判断符号看第 1 位即可：格式固定为「变量符号符号变量」，等式是 ==、不等式是 !=，第 1 位分别是 = 与 !，两者互斥且无需看第 2 位。

union(a, b) 先各自 find 到根再挂接。直接写 parent[a] = b 是错的——a 可能已经不是自己那一类的根，改写它只会把 a 这一个节点摘出去，把它原来的整棵子树留在旧类里，等价类会被撕裂。必须挂根到根。

find 中做路径压缩。递归版在回溯时把沿途所有节点直接指向根，把树高压平；不压缩时，链式合并（a==b, b==c, c==d, ...）会退化成一条长链，每次 find 都要走满全长。有了压缩，均摊代价接近常数。

第二趟检查所有 != 方程，一旦两端 find 结果相同立刻 return false。之所以能立刻返回，是因为只要存在一个矛盾，整个方程组就不可满足，后面的方程无论如何都救不回来。

全部检查通过返回 true。这一步依赖前面「不同等价类可任意取不同值」的论证：没有矛盾就必然有解，不需要真的去构造一组赋值来验证。

以 equations = ["a==b", "b!=c", "c==a"] 走一遍。初始 parent[i] = i，即 a、b、c 各自成类（下标 0、1、2）。

第一趟处理等式。"a==b"：a 是 0、b 是 1，find(0) = 0、find(1) = 1，两根不同，令 parent[0] = 1，此时 {a, b} 合成一类，代表元是 b。"b!=c" 第 1 位是 !，本趟跳过。"c==a"：c 是 2、a 是 0，find(2) = 2，find(0) 走到 parent[0] = 1，parent[1] = 1 是根，返回 1 并顺手把 parent[0] 压成 1（本来就是 1）；两根 2 与 1 不同，令 parent[2] = 1。至此 {a, b, c} 全部并入代表元 b 这一类。

第二趟检查不等式。"b!=c"：find(1) = 1，find(2) 走到 parent[2] = 1 返回 1，两者相同，说明前面的等式已经强制 b 与 c 相等，与本条不等式直接冲突，返回 false。手工核对：a == b 与 c == a 联立推出 b == c，确实与 b != c 矛盾，无解，答案正确。

再看一个正例 equations = ["b==a", "a==c", "b!=d"]。第一趟："b==a" 令 parent[1] = 0；"a==c" 中 find(0) = 0、find(2) = 2，令 parent[0] = 2，此时 {a, b, c} 同类、代表元 c，d 仍独立。第二趟："b!=d" 中 find(1) 经 parent[1] = 0 再到 parent[0] = 2 得到 2，并把 parent[1] 压缩成 2；find(3) = 3，2 ≠ 3 不冲突。全部通过，返回 true。实际赋值可取 a = b = c = 0、d = 1，三条方程同时成立。

代码实现

// 再检查所有不等式 a!=b，若同属一集合则矛盾。
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;
        }
    }
}

// 再检查所有不等式 a!=b，若同属一集合则矛盾。
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
}

复杂度分析

时间复杂度：$O(n \cdot \alpha(26))$，其中 n 为方程数量，$\alpha$ 是反阿克曼函数。凭什么？初始化固定 26 步；两趟扫描各处理 n 个方程，每个方程只做常数次 find，而带路径压缩的 find 均摊代价是 $\alpha$ 级别，在 26 个元素的规模下实际就是常数。整体可以粗略视为线性。

空间复杂度：$O(1)$。凭什么？额外结构只有长度恒为 26 的 parent 数组，与输入方程数量 n 无关；Java 版 find 的递归栈深度受并查集树高限制，路径压缩后同样是常数级，不随 n 增长。

关键点总结

「相等」自带传递性，看到它就该想等价类：一切「A 与 B 同组、同值、同账户、可互换」的约束都在描述等价关系，而并查集正是等价关系的标准实现。识别关系的代数性质（自反、对称、传递）比死记题型更能迁移。

约束分两类时先处理「构造型」再处理「否决型」：等式在构造闭包、不等式在做否决，前者的结果是后者的判断依据，顺序不能反。这个「先建后验」的两趟模式在冲突检测类题目里非常通用，写代码前先明确哪一类必须先行。

判定条件的充分性要能说清：不冲突就一定有解，理由是不同等价类可以自由取不同整数，而变量个数有限、整数无限。面试时补上这句，说明你验证的是充要条件而不是只做了必要性检查。

union 必须挂根到根：parent[find(a)] = find(b) 与 parent[a] = find(b) 只差一个 find，后者会撕裂已有集合。这是并查集最高频的实现错误，写模板时把 find 写在赋值左侧是肌肉记忆的一部分。

值域固定时用数组替代哈希：26 个小写字母意味着 ch - 'a' 直接当下标，比 Map<Character, Character> 更快也更短。看到「只含小写字母」「只有数字 0-9」这类描述，优先考虑定长数组。

面试视角：这题是并查集的入门检验，写完后主动说出两点会加分——一是「不等式没有传递性所以不能一起合并」，二是「按秩合并可以进一步把树高压到 $O(\log n)$，但在 26 个元素规模下路径压缩已经足够，为了白板简洁我只写了压缩」。若面试官追问变体，可以提到「若把 != 换成 <，等价类就不够用了，需要转成图上的环检测/差分约束」。

易错点总结

错误写法：把等式与不等式放在同一趟循环里处理。用例 ["a!=b", "a==b"] → 遍历到第一条时 a、b 还没合并，find 结果不同判为不冲突；第二条把它们合并后循环就结束了，最终返回 true；正确答案是 false。必须先合并所有 ==，再统一检查 !=。

错误写法：union 里写成 parent[a] = b 而不是 parent[find(a)] = find(b)。用例 ["b==a", "b==c", "a!=c"] → 第一条写 parent[b] = a，第二条又直接写 parent[b] = c 把上一次的挂接覆盖掉，a 被独自留在原地，最后 find(a) = a、find(c) = c 两根不同返回 true；正确答案是 false（由 b == a 与 b == c 推出 a == c）。

错误写法：判断符号时看 eq.charAt(2) 而不是 eq.charAt(1)。用例 ["a!=a"] → 第 2 位是 =，这条不等式被误当成等式去做合并，而第二趟的 charAt(2) == '!' 永远不成立，没有任何方程被检查，直接返回 true；正确答案是 false。== 与 != 的第 2 位都是 =，唯一的区分点在第 1 位。

错误写法：取变量时用 eq.charAt(2) 当右操作数。用例 ["a==b"] → 右侧取到的是 '='，'=' - 'a' 得到负数 -36，parent[-36] 直接数组越界抛异常。格式固定为四字符，右操作数永远在下标 3。

错误写法：为 "a!=a" 单写一个 return false 分支，却忘了 "a==a" 也要放行。用例 ["a==a"] → 若把「两端字母相同」一律判为矛盾，会返回 false；正确答案是 true，因为 a == a 恒成立。反过来，"a!=a" 无需特判，通用逻辑里 find(a) == find(a) 必然成立会自动返回 false。

错误写法：find 不做路径压缩。用例是 5000 条形如 "a==b", "b==c", ... 但变量顺序刻意构成长链的方程（26 个字母下链长有限，但在变量数扩大的加强版里）→ 树退化成链，每次 find 都要走 $O(n)$ 步，总代价升到 $O(n^2)$。本题因为只有 26 个变量不会真的超时，但一旦把模板复制到变量数上万的题目就会 TLE。

错误写法：Go 版把 find 写成值传递的普通函数而不是闭包，或在闭包里对 parent 重新赋值。用例任意含 == 的输入 → 若 find 内部对切片元素的修改没有作用在同一底层数组上（例如误写 parent = append([]int{}, parent...) 做了拷贝），路径压缩与合并全部丢失，["a==b", "a!=b"] 会返回 true 而不是 false。切片作为闭包捕获变量时共享底层数组，不要中途替换整个切片。

错误写法：Java 版把 find 写成迭代但忘了更新 x。写成 while (parent[x] != x) { parent[x] = parent[parent[x]]; } 而漏掉 x = parent[x]，用例 ["a==b", "b==c", "a!=c"] → 循环条件在 parent[x] 被压缩后可能仍不等于 x，陷入死循环直到超时。路径减半写法里赋值与前进两步缺一不可。

错误写法：用 Map<Character, Character> 存 parent 但忘了给首次出现的变量做初始化。用例 ["c==c"] → map.get('c') 返回 null，拆箱时抛 NPE。定长数组天然规避这个问题，这也是本题优先用数组的原因之一。

错误写法：第二趟遍历时用第一趟已经缓存下来的 find 结果。用例 ["a==b", "b!=c", "c==a"] → 若在第一趟处理 "b!=c" 的位置就记录下当时的根并留到最后比较，会用到「c 尚未并入」的过期状态，返回 true；正确答案是 false。所有 find 都必须在全部合并完成之后重新调用。

相似题目

题目	难度	考察点
547. 省份数量	中等	只需数出连通块个数，没有第二类「否决型」约束，一趟合并后统计根即可
684. 冗余连接	中等	在合并过程中检测环，冲突发生的时刻本身就是答案，不能拆成先建后验两趟
721. 账户合并	中等	元素是任意字符串需先哈希编号，且合并完还要按根聚合并排序输出具体分组
1202. 交换字符串中的元素	中等	连通块内下标可任意置换，需对每个块的字符排序后回填以求字典序最小
765. 情侣牵手	困难	答案是「节点数减连通块数」的最少交换次数，考察把交换问题映射成连通块计数
128. 最长连续序列	中等	边由数值相邻隐式给出而非显式列出，还需额外维护每个集合的大小