Consistent Equalities
Problem
Each constraint is a four-character string over single lowercase letters, either "x==y" or "x!=y". Decide whether you can give every letter an integer value so that all the constraints hold at once.
Examples
Input: rules = ["a==b", "b!=a"]
Output: FalseInput: rules = ["a==b", "b==c", "c!=d", "a!=d"]
Output: True
Why: give a, b and c one value and d anotherInput: rules = ["a!=a"]
Output: False
Why: edge case, a letter can never differ from itselfHints
0 / 3
Equalities chain together: if a equals b and b equals c, then a equals c even though no rule says so directly. Inequalities do not chain at all.
Handle the two kinds of rule separately. The equalities alone decide which letters are forced to share a value.
First pass: union the two letters of every equality in a disjoint-set structure. Second pass: for every inequality, if both letters have the same root, return False. If no inequality fails, return True.
Solution
Only the equalities force letters together, and they do so transitively, so merging them in a disjoint-set structure produces exactly the groups of letters that must share a value. Giving each group its own distinct value then satisfies every equality, and it satisfies every inequality whose letters sit in different groups. So an inequality fails precisely when both of its letters landed in the same group, including the case of a letter compared with itself. Processing all the equalities before any inequality is essential. With 26 letters, time is O(n) over the rules and space is O(1).
def consistent(rules):
parent = {c: c for c in "abcdefghijklmnopqrstuvwxyz"}
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
for r in rules:
if r[1] == "=": # phase 1: merge the equalities
parent[find(r[0])] = find(r[3])
for r in rules:
if r[1] == "!" and find(r[0]) == find(r[3]): # phase 2: test the rest
return False
return True
print(consistent(["a==b", "b!=a"])) # -> False
print(consistent(["a==b", "b==c", "c!=d", "a!=d"])) # -> True
print(consistent(["a!=a"])) # -> FalseStuck on the idea rather than the code? Path Compression covers it.