Show problems as
Classic problem #990MediumArrayStringUnion-FindGraph Theory

Satisfiability of Equality Equations

Real-world version: Consistent Terminal Voltage Claims
Tracked in this browser only
Read Satisfiability of Equality Equations on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A test rig has terminals labelled with single lowercase letters. A technician hands you claims, a list of measurements each written as exactly four characters:

  • claims[i][0] and claims[i][3] are the two terminal labels;
  • claims[i][1] is '=' when the claim is that the two terminals carry the same voltage, or '!' when the claim is that they carry different voltages;
  • claims[i][2] is always '='.

So "c==d" claims terminals c and d sit at one voltage, and "c!=d" claims they do not. A claim may name the same terminal on both sides.

Decide whether some assignment of an integer voltage to every terminal label makes all the claims hold at the same time. Return true if such an assignment exists and false otherwise.

Examples

Example 1

Input
claims = ["r==s", "s==t", "t!=r"]
Output
false

The first two claims put `r`, `s` and `t` all at one voltage, which leaves the third claim asking for `t` and `r` to differ while they are forced to agree.

Example 2

Input
claims = ["h==j", "k!=j", "h==m"]
Output
true

Setting `h`, `j` and `m` to 4 and `k` to 9 satisfies every claim: the two sameness claims hold and `k` differs from `j`.

Example 3

Input
claims = ["w!=w"]
Output
false

The claim asks terminal `w` to carry a voltage different from its own, which no assignment can do.

Constraints

  • 1 <= claims.length <= 500
  • claims[i].length == 4
  • claims[i][0] is a lowercase English letter.
  • claims[i][1] is either '=' or '!'.
  • claims[i][2] is '='.
  • claims[i][3] is a lowercase English letter.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def claims_consistent(claims: list[str]) -> bool:
Java
public boolean claimsConsistent(String[] claims)

More on the same topics