-
Notifications
You must be signed in to change notification settings - Fork 0
/
Satisfiability of Equality Equations.py
82 lines (65 loc) · 2.42 KB
/
Satisfiability of Equality Equations.py
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class Solution:
def equationsPossible(self, equations: List[str]) -> bool:
if not equations:
return False
var_map = dict()
i = 0
for equation in equations:
a, b = equation[0], equation[3]
eq = equation[1]
if a == b and eq == '!':
return False
i += 2
# both exists - compare
if a in var_map and b in var_map:
if (eq == '!' and var_map[a]==var_map[b]) or (eq == '=' and var_map[a]!=var_map[b]):
return False
# both doesn't exist - initialize both var
elif a not in var_map and b not in var_map:
if eq == '!':
var_map[a] = i
var_map[b] = i+1
else:
var_map[a] = var_map[b] = i
# 1 exist, 1 doesn't - define one by another
else:
if a in var_map:
if eq == '!':
var_map[b] = i
else:
var_map[b] = var_map[a]
else:
if eq == '!':
var_map[a] = i
else:
var_map[a] = var_map[b]
return True
# Disjoint Set Union (dsu) aka Union Find
# https://leetcode.com/problems/satisfiability-of-equality-equations/discuss/2625039/LeetCode-The-Hard-Way-Explained-Line-By-Line
class Solution:
def equationsPossible(self, equations: List[str]) -> bool:
# ["a==b","b!=a"] False
# ["b==a","a==b"] True
# ["a==b","b==c","c!=a"] False
# ["a!=a"] False
# ["a==b","a==c","c!=b"] False
# ["a==b","c==a","c!=b"] False
parent = [i for i in range(26)]
def find(x):
if parent[x] == x:
return x
return find(parent[x])
for e in equations:
a = ord(e[0]) % 97
b = ord(e[3]) % 97
eq = e[1]
if eq == '=':
parent[find(a)] = find(b)
for e in equations:
a = ord(e[0]) % 97
b = ord(e[3]) % 97
eq = e[1]
if eq == '!' and find(a) == find(b):
return False
return True
# time: O(Nlog(N)), space: O(1)