Satisfiability of Equality Equations
Medium · Graphs · Array · String · Union Find · Graph
Problem
You are given equations, a list of 4-character strings. Each has the form "x==y" or "x!=y", where x and y are single lowercase letters naming integer variables (the two letters may be the same).
Return true if you can assign an integer to every variable so that all the equations hold at once, and false otherwise.
Examples
Input: equations = ["p==q","q==r","p!=r"] Output: false
p, q and r must all be equal, so p cannot differ from r.
Input: equations = ["m==n","n!=k"] Output: true
Set m = n = 1 and k = 2.
Input: equations = ["z!=z"] Output: false
A variable can never differ from itself.
Constraints
- 1 <= len(equations) <= 500
- len(equations[i]) == 4
- equations[i][0] and equations[i][3] are lowercase letters
- equations[i][1:3] is "==" or "!="
Approaches
- Graph search for every inequality — time O(n · (n + 26)), space O(n)
Follow-up
Why two passes? An inequality read before the equalities that break it would pass a one-pass check. The use cases answer "must these two be equal?" queries from the same grouping, and find the first equation at which the system becomes impossible.
Related problems
Start free on Cariara · Coding problems · System design studio
