1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution:
def equationsPossible(self, equations: List[str]) -> bool:
# Union-Find function to find the parent of a variable
def find(x):
if x != parent[x]:
parent[x] = find(parent[x])
return parent[x]
# Union-Find function to unite two variables
def union(x, y):
parent[find(x)] = find(y)
# Initialize parents for each variable
parent = [i for i in range(26)]
# Process '==' equations first, unifying the variables
for equation in equations:
if equation[1] == '=':
x = ord(equation[0]) - ord('a')
y = ord(equation[3]) - ord('a')
union(x, y)
# Process '!=' equations, checking for inconsistency
for equation in equations:
if equation[1] == '!':
x = ord(equation[0]) - ord('a')
y = ord(equation[3]) - ord('a')
if find(x) == find(y): # Inconsistent if x and y are in the same set
return False
return True
|