Problem Breakdown
We are given a list of equations involving single-character lowercase English letters. Each equation is either an equality (a==b) or an inequality (a!=b). The goal is to determine if there exists any assignment of integer values that satisfies all constraints simultaneously.
Key Constraints:
- Transitivity: If
a == bandb == c, thenamust equalc. Equality forms connected components (equivalence classes). - Inequality Check: An inequality (
a != b) is only valid ifaandbare in different equivalence classes. If they end up in the same class due to equality chains, a contradiction exists.
Intuition
A brute-force approach attempting all integer assignments is impossible because integers can be arbitrarily large; we care about relative values (equality vs inequality). The problem maps naturally to graph theory: variables are nodes, and == constraints define edges merging components.
Core Insight:
- Build Components: Use a Disjoint Set Union (DSU) structure where all equality (
==) operations merge the sets of their respective variables. - Validate Contradictions: After processing all equalities, iterate through inequality (
!=) constraints. If two variables in ana != bconstraint belong to the same set (connected component), it is impossible to satisfy both the implied equality chain and the explicit inequality. ReturnFalse. Otherwise, returnTrue.
Approach
- Initialize DSU: Create a parent array for all lowercase letters (‘a’-‘z’), where each index initially points to itself (
parent[i] = i). This represents that every variable is its own set leader initially. - Process Equalities (Pass 1): Iterate through the
equationslist. For any equation containing'==', perform a union operation on the two variables involved. The union function finds their roots and links one root to another, merging the sets. Path compression is used in the find operation to keep tree height low. - Process Inequalities (Pass 2): Iterate through
equationsagain. For any equation containing'!=', check if the two variables share the same root using thefindfunction. If they do, a contradiction exists; returnFalse. - Return Result: If all inequality checks pass without finding connected components that should be unequal, return
True.
Complexity Analysis
- Time Complexity: , where is the number of equations and is the inverse Ackermann function (nearly constant). Since the alphabet size is fixed, this simplifies to effectively linear time relative to input length: .
- Space Complexity: for the parent array where . This is considered constant space () with respect to the number of equations.
Solution
class Solution:
def equationsPossible(self, equations):
# Initialize DSU structure with 26 nodes ('a' -> 0 to 'z' -> 25)
parent = list(range(26))
# Find function with path compression for efficiency
def find(i):
if parent[i] != i:
parent[i] = find(parent[i])
return parent[i]
# Union function to merge two sets
def union(i, j):
root_i = find(i)
root_j = find(j)
if root_i != root_j:
parent[root_i] = root_j
# First pass: Process all equality constraints (==)
for eq in equations:
u = ord(eq[0]) - 97 # 'a' is ASCII 97
v = ord(eq[3]) - 97
if eq[1] == '=':
union(u, v)
# Second pass: Check all inequality constraints (!=) against the built structure
for eq in equations:
u = ord(eq[0]) - 97
v = ord(eq[3]) - 97
if eq[1] == '!':
# If 'u' and 'v' are already connected, this inequality is impossible to satisfy
if find(u) == find(v):
return False
return True
# Example usage:
# sol = Solution()
# print(sol.equationsPossible(["a==b","b!=c"]))
Edge Cases Handled
- Self-Equality (
"c==c"): Theunionfunction handles this gracefully; finding the root of ‘c’ twice results in no change, which is correct. - Redundant Equalities: Multiple
"a==b", "b==a"are handled by DSU’s idempotent nature (merging already merged sets does nothing). - Contradictory Inequalities (
"a!=c"whereaandcbecome connected via other equations): The second pass explicitly checks if inequality nodes share a root. If they do, it returnsFalse. - Disconnected Variables: Variables that never appear in any equation remain isolated (root = self), satisfying all constraints involving them trivially unless an explicit constraint links them to others.