Very fun question. We’re given a list of equations of the format “a==b” or “b!=a” and we’re asked to determine if the set of equations is satisfiable. All variables in these equations are lowercase, and the equations are only the two inequalities ”==” and ”!=“.
To solve this, we treat "" as an undirected edge for the two nodes represented by the variables of the equation. We treat "" as reflective and transitive, so if ab and bc, then a==c. Given this, we can store variables that are equal in disjoint sets. When we evaluate all “!=” equations, we see if the two variables are in the same disjoint set - this would be a contradiction for our set of equations, so we return False. If we don’t find any contradictions, we return True.
The solution is as follows:
from collections import defaultdict
class UnionFind:
def __init__(self, n: int) -> None:
self.rank, self.parent = [1 for _ in range(n)], [i for i in range(n)]
def find(self, x: str) -> str:
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union_set(self, x: str, y: str) -> None:
xset, yset = self.find(x), self.find(y)
if xset != yset:
if self.rank[xset] < self.rank[yset]:
xset, yset = yset, xset
self.parent[yset] = xset
self.rank[xset] += self.rank[yset]
class Solution:
def equationsPossible(self, equations: List[str]) -> bool:
uf = UnionFind(26)
for equation in equations:
if equation[1] == "=":
u, v = ord(equation[0]) - ord("a"), ord(equation[3]) - ord("a")
uf.union_set(u, v)
for equation in equations:
if equation[1] == "!":
u, v = ord(equation[0]) - ord("a"), ord(equation[3]) - ord("a")
if uf.find(u) == uf.find(v):
return False
return True_ Time Complexity:
O(n) - We execute find or union_set at most n times.
_ Space Complexity:
O(1) - Our storage requirements are constant, 26 characters.