990. Satisfiability of Equality Equations LeetCode Solution
In this guide, you will get 990. Satisfiability of Equality Equations LeetCode Solution with the best time and space complexity. The solution to Satisfiability of Equality Equations problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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.
990. Satisfiability of Equality Equations LeetCode Solution in C++
class UnionFind {
public:
UnionFind(int n) : id(n) {
iota(id.begin(), id.end(), 0);
}
void union_(int u, int v) {
id[find(u)] = find(v);
}
int find(int u) {
return id[u] == u ? u : id[u] = find(id[u]);
}
private:
vector<int> id;
};
class Solution {
public:
bool equationsPossible(vector<string>& equations) {
UnionFind uf(26);
for (const string& e : equations)
if (e[1] == '=') {
const int x = e[0] - 'a';
const int y = e[3] - 'a';
uf.union_(x, y);
}
for (const string& e : equations)
if (e[1] == '!') {
const int x = e[0] - 'a';
const int y = e[3] - 'a';
if (uf.find(x) == uf.find(y))
return false;
}
return true;
}
}; /* code provided by PROGIEZ */
990. Satisfiability of Equality Equations LeetCode Solution in Java
class UnionFind {
public UnionFind(int n) {
id = new int[n];
rank = new int[n];
for (int i = 0; i < n; ++i)
id[i] = i;
}
public void unionByRank(int u, int v) {
final int i = find(u);
final int j = find(v);
if (i == j)
return;
if (rank[i] < rank[j]) {
id[i] = j;
} else if (rank[i] > rank[j]) {
id[j] = i;
} else {
id[i] = j;
++rank[j];
}
}
public int find(int u) {
return id[u] == u ? u : (id[u] = find(id[u]));
}
private int[] id;
private int[] rank;
}
class Solution {
public boolean equationsPossible(String[] equations) {
UnionFind uf = new UnionFind(26);
for (final String e : equations)
if (e.charAt(1) == '=') {
final int x = e.charAt(0) - 'a';
final int y = e.charAt(3) - 'a';
uf.unionByRank(x, y);
}
for (final String e : equations)
if (e.charAt(1) == '!') {
final int x = e.charAt(0) - 'a';
final int y = e.charAt(3) - 'a';
if (uf.find(x) == uf.find(y))
return false;
}
return true;
}
} // code provided by PROGIEZ
990. Satisfiability of Equality Equations LeetCode Solution in Python
class UnionFind:
def __init__(self, n: int):
self.id = list(range(n))
def union(self, u: int, v: int) -> None:
self.id[self.find(u)] = self.find(v)
def find(self, u: int) -> int:
if self.id[u] != u:
self.id[u] = self.find(self.id[u])
return self.id[u]
class Solution:
def equationsPossible(self, equations: list[str]) -> bool:
uf = UnionFind(26)
for x, op, _, y in equations:
if op == '=':
uf.union(string.ascii_lowercase.index(x),
string.ascii_lowercase.index(y))
return all(
uf.find(string.ascii_lowercase.index(x)) !=
uf.find(string.ascii_lowercase.index(y))
for x, op, _, y in equations
if op == '!') # code by PROGIEZ
