Satisfiability of Equality Equations
01 · Problem
You are given an array of strings equations. Each string has exactly 4 characters and is either "x==y" or "x!=y", where x and y are lowercase letters (possibly the same letter) acting as single-letter variable names.
Return true if it is possible to assign an integer to every variable so that all equations hold at the same time, and false otherwise.
02 · Examples
equations = ["a==b","b!=a"]
false
The first equation forces a and b to be equal, which contradicts the second.
equations = ["x==y","y==z","x!=z"]
false
Equality is transitive: x == y and y == z mean x == z, contradicting x != z.
equations = ["a==b","c!=d","b==c"]
true
Give a, b, c the value 1 and d the value 2. Every equation holds.
03 · Constraints
- 011 <= equations.length <= 500
- 02equations[i].length == 4
- 03equations[i][0] and equations[i][3] are lowercase English letters
- 04equations[i][1] is '=' or '!'
- 05equations[i][2] is '='
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.