LeetCode 题解工作台
等式方程的可满足性
给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4 ，并采用两种不同的形式之一： "a==b" 或 "a!=b" 。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。 只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 t…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·string
答案摘要
class Solution: def equationsPossible(self, equations: List[str]) -> bool:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·string 题型思路
题目描述
给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 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 <= equations.length <= 500equations[i].length == 4equations[i][0]和equations[i][3]是小写字母equations[i][1]要么是'='，要么是'!'equations[i][2]是'='
解题思路
方法一
class Solution:
def equationsPossible(self, equations: List[str]) -> bool:
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
p = list(range(26))
for e in equations:
a, b = ord(e[0]) - ord('a'), ord(e[-1]) - ord('a')
if e[1] == '=':
p[find(a)] = find(b)
for e in equations:
a, b = ord(e[0]) - ord('a'), ord(e[-1]) - ord('a')
if e[1] == '!' and find(a) == find(b):
return False
return True
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate understands the Union Find technique and its use in grouping variables based on equality.
- question_mark
The candidate optimizes the Union Find operations using path compression, improving the solution's efficiency.
- question_mark
The candidate successfully handles edge cases, such as conflicts between equality and inequality constraints, demonstrating problem-solving skills.
常见陷阱
外企场景- error
Failing to consider edge cases where inequality conflicts with existing equality relationships.
- error
Not optimizing the Union Find operations with path compression, leading to slower performance for larger test cases.
- error
Confusing the order of processing equality and inequality equations, which may lead to incorrect results.
进阶变体
外企场景- arrow_right_alt
Use a different data structure for union-find, such as a disjoint set with additional optimizations.
- arrow_right_alt
Extend the problem to handle more complex relationships, such as multiple inequalities between the same variables.
- arrow_right_alt
Apply the solution to solve similar problems involving graph connectivity or equivalence of nodes.