0990. Satisfiability of Equality Equations

题目信息

题号:

0990

难度:

Medium

主题:

等式约束、变量关系、可满足性

原题:

LeetCode 0990

重点:

每条方程只涉及两个小写变量和运算符 == 或 !=;需要判断是否能为全部变量赋值,使所有等式与不等式同时成立

题目重述

给定字符串数组 equations。每个字符串长度恰好为 4,格式为 "a==b" 或 "a!=b",其中两端是小写英文字母表示的变量。

判断是否存在一组变量取值,使数组中的所有相等和不等约束同时成立。相等关系具有传递性,例如 a == b 且 b == c 会要求 a == c;若任何不等式与这些相等关系冲突,则不可满足。

1 <= equations.length <= 500,变量来自 a 至 z。

自建示例

传递相等关系与不等式冲突:

输入:equations = ["a==b","b!=c","c==a"]
输出:false
解释:a == b 且 c == a 推出 b == c,但数组同时要求 b != c,因此不存在满足全部方程的赋值。

变量不能与自身不相等:

输入:equations = ["x!=x"]
输出:false
解释:任何赋值都满足 x 与自身相等,因此约束 x != x 不可能成立。