0990. Satisfiability of Equality Equations¶
题目信息¶
- 题号:
0990
- 难度:
Medium
- 主题:
等式约束、变量关系、可满足性
- 原题:
- 重点:
每条方程只涉及两个小写变量和运算符
==或!=;需要判断是否能为全部变量赋值,使所有等式与不等式同时成立
题目重述¶
给定字符串数组 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 不可能成立。