Algorithm
Problem Name: 990. 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 <= 500equations[i].length == 4equations[i][0]is a lowercase letter.equations[i][1]is either'='or'!'.equations[i][2]is'='.
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean equationsPossible(String[] equations) {
List[] graph = new ArrayList[26];
for (int i = 0; i < 26; i++) {
graph[i] = new ArrayList<>();
}
for (String equation : equations) {
if (equation.charAt(1) == '=') {
int first = equation.charAt(0) - 'a';
int second = equation.charAt(3) - 'a';
graph[first].add(second);
graph[second].add(first);
}
}
int[] color = new int[26];
Arrays.fill(color, -1);
for (int i = 0; i < 26; i++) {
if (color[i] == -1) {
dfs(i, i, color, graph);
}
}
for (String equation : equations) {
if (equation.charAt(1) == '!') {
int first = equation.charAt(0) - 'a';
int second = equation.charAt(3) - 'a';
if (color[first] == color[second]) {
return false;
}
}
}
return true;
}
private static void dfs(int node, int nodeColor, int[] color, List < Integer>[] graph) {
if (color[node] == -1) {
color[node] = nodeColor;
for (int neighbor : graph[node]) {
dfs(neighbor, nodeColor, color, graph);
}
}
}
}
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const equationsPossible = function(equations) {
const uf = new Array(26).fill(0);
const aCode = ('a').charCodeAt(0)
for (let i = 0; i < 26; ++i) uf[i] = i;
for (let e of equations)
if (e.charAt(1) === '=')
uf[find(e.charCodeAt(0) - aCode)] = find(e.charCodeAt(3) - aCode);
for (let e of equations)
if (e.charAt(1) === '!' && find(e.charCodeAt(0) - aCode) === find(e.charCodeAt(3) - aCode))
return false;
return true;
function find(x) {
if (x != uf[x]) uf[x] = find(uf[x]);
return uf[x];
}
};
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def equationsPossible(self, equations: List[str]) -> bool:
def uf(c):
return uf(parent[ord(c) - ord('a')]) if parent[ord(c) - ord('a')] != c else ord(c) - ord('a')
parent = [c for c in string.ascii_lowercase]
for eq in equations:
if eq[1] == '=':
parent[uf(eq[0])] = parent[uf(eq[-1])]
for eq in equations:
if eq[1] == '!' and parent[uf(eq[0])] == parent[uf(eq[-1])]:
return False
return True
Input
Output