LeetCode Satisfiability of Equality Equations Solution

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.

Problem Link: https://leetcode.com/problems/satisfiability-of-equality-equations/



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