Consistent Letter Equations

Medium

Variables are named by lowercase English letters. You get a list of rules rules; each rule is a four-character string of one of two kinds: - "a==b": variables a and b are equal; - "a!=b": variables a and b are different. The two letters in a rule may be the same. Return True if integers can be assigned to the variables so that all rules hold at once, otherwise False.

Example 1

rules=["p==q", "q==r", "r!=p"] → False

The first two rules force p, q and r to be equal, so r != p cannot hold.

Example 2

rules=["x!=y", "y==z", "x==x"] → True

For example x = 1, y = z = 2 satisfies every rule.

Example 3

rules=["k!=k"] → False

Constraints

1 ≤ len(rules) ≤ 500
len(rules[i]) == 4
rules[i][0] and rules[i][3] are lowercase English letters
rules[i][1:3] is either "==" or "!="

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Union Find Graph Array String

Similar problems

Ratio Chain Queries Medium Merge Contact Cards Medium Chains of Synonyms Medium Rearrange Through Links Medium Every Rewording of a Sentence Medium

Input

rules=["p==q", "q==r", "r!=p"]

Expected

False

Run checks the first 3 tests in your browser. Submit checks all 85 tests on the server, hidden ones included.