582. Satisfiability of Equality Equations
Your function receives equations, an array of strings that are each exactly 4 characters long and constrain single-letter variables: "x==y" demands that variables x and y hold the same value, and "x!=y" demands that they differ. Variable names are lowercase letters, so there are at most 26 of them.
Return true if some assignment of integers to the variables satisfies every equation at once, and false if the equations contradict each other.
Equality is contagious: if a == b and b == c, then a and c are forced equal even though no equation says so directly. A single != between two variables trapped in the same equality group sinks the whole system.
Example 1:
Input: equations = ["a==b", "b!=a"]
Output: false
Explanation: The first equation forces a and b to be equal; the second forbids exactly that. No assignment can do both.
Example 2:
Input: equations = ["b==a", "a==b"]
Output: true
Explanation: Both equations say the same thing. Assign a = b = 0 and every constraint holds.
Constraints:
- 1 ≤ equations.length ≤ 500
- equations[i].length == 4
- equations[i][0] and equations[i][3] are lowercase letters
- equations[i][1] is '=' or '!' and equations[i][2] is '='
Hints:
Process the two kinds of constraints in separate phases. The == equations only ever merge variables into groups; the != equations only ever test whether a merge went too far.
After all merges, the variables split into clusters where everything must share one value. An inequality x!=y is violated exactly when x and y ended up in the same cluster — and x!=x is always a contradiction.
"Merge groups, then ask if two elements share a group" is precisely what a union-find (disjoint set union) structure does in near-constant time per operation.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: equations = ["a==b", "b!=a"]
Expected output: false