Satisfiability of Equality Equations medium
Description
You are given an array of strings equations that represent relationships between variables where each string is of length 4 and takes one of two forms: "a==b" or "a!=b". Here, a and b are lowercase letters representing one-letter variable names.
Return true if it is possible to assign integers to variable names so as to satisfy all the given equations, or false otherwise.
Examples
> Case 1:
equations = ["a==b","b!=a"]
Output: false # a==b says a, b are the same; b!=a says they differ. Contradiction.
> Case 2:
equations = ["b==a","a==b"]
Output: true
> Case 3:
equations = ["a==b","b==c","a==c"]
Output: true
> Case 4:
equations = ["a==b","b==c","a!=c"]
Output: falseConstraints
1 <= equations.length <= 500- Each equation is exactly 4 characters long.
- Variables are single lowercase English letters.
State design
Equalities form an equivalence relation: a == b and b == c implies a == c. That’s DSU’s bread and butter.
Two-pass approach:
- Pass 1 — process all
==equations. Union the two variables in each. After this pass, the DSU groups represent equivalence classes. - Pass 2 — verify all
!=equations. For eacha != b, iffind(a) == find(b), the inequality contradicts an established equivalence. Returnfalse.
If pass 2 finds no contradictions, return true.
26 variables max (lowercase letters), so size the DSU to 26 and index by ord(c) - ord('a').
Code
Analysis
- Time:
O(N · α(26)) = O(N)— two passes, near-constant per operation. - Space:
O(1)— fixed 26-element DSU.
Order matters. Process all equalities before any inequality. If you interleave, an inequality might pass simply because the equality that contradicts it hasn’t been seen yet. The two-pass structure is the whole trick.
Same skin
- Lexicographically Smallest Equivalent String — DSU keeping the smallest character as the root.
- Evaluate Division — equality with multiplicative offsets → weighted DSU.
- Possible Bipartition — DSU with parity coloring.