754. Equation Consistency
A museum curator labels 26 display cases with the letters a to z. Every case holds items from exactly one era, but the eras are unknown. A list of notes equations records claims, each exactly four characters long: "x==y" says cases x and y hold items from the same era, and "x!=y" says they hold items from different eras.
Return true if the eras can be assigned to the cases so that every note is true at the same time, and false otherwise. A case may appear on both sides of a note, and an arbitrary number of different eras is available.
Example 1
- Input:
- equations = ["p==q","q==r","p!=r"]
- Output:
- false
- Explanation:
The first two claims force p, q and r into the same era, which contradicts the claim that p and r differ.
Example 2
- Input:
- equations = ["m==n","n!=o","o==p","p!=m"]
- Output:
- true
- Explanation:
Assign m and n to one era and o and p to another; every claim holds.
Example 3
- Input:
- equations = ["a==b","b==c","c==d","d!=a"]
- Output:
- false
- Explanation:
Equality chains from a to d, so claiming that d differs from a is impossible.
Constraints
- 1 ≤ equations.length ≤ 105
- equations[i] has length 4 and has the form
x==yorx≠y - x and y are lowercase English letters
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(m * alpha(26))
- Space
- O(1)