Satisfiability of Equality Equations
You are given an array of strings equations
that represent relationships between variables where each string equations[i]
is of length 4
and takes one of two different forms: "xi==yi"
or "xi!=yi"
.Here, xi
and yi
are lowercase letters (not necessarily different) that represent one-letter variable names.
Return true
if it is possible to assign integers to variable names so as to satisfy all the given equations, or false
otherwise.
Example 1:
Input: equations = ["a==b","b!=a"]
Output: false
Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second.
There is no way to assign the variables to satisfy both equations.
Example 2:
Input: equations = ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.
Constraints:
1 <= equations.length <= 500
equations[i].length == 4
equations[i][0]
is a lowercase letter.equations[i][1]
is either'='
or'!'
.equations[i][2]
is'='
.equations[i][3]
is a lowercase letter.
Solution
We will use DSU for this question with two passes on equations
.
In the first pass, we join the variables that are equal into one component. In the second pass, we check whether two variables in an inequality expression are indeed in different components. If we arrive at a contradition, then the equality equations are not satisfiable.
Implementation
1def equationsPossible(self, equations: List[str]) -> bool:
2 equality = {}
3 def find(x):
4 y = equality.get(x, x)
5 if y != x:
6 equality[x] = y = find(y)
7 return y
8 def union(x, y):
9 equality[find(x)] = find(y)
10
11 for eq in equations:
12 if eq[1] == '=':
13 union(eq[0], eq[3])
14 for eq in equations:
15 if eq[1] == '!' and find(eq[0]) == find(eq[3]):
16 return False
17 return True
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.