## DEV Community

Abhishek Chaudhary

Posted on

# 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:

``````class Solution:
def equationsPossible(self, equations: List[str]) -> bool:
equalGraph = {}
inequalities = []
for eq in equations:
a = eq[0]
b = eq[-1]
opr = eq[1:-1]
if opr == "==":
equalGraph[a] = equalGraph.get(a, []) + [b]
equalGraph[b] = equalGraph.get(b, []) + [a]
else:
inequalities.append((a, b))
for a, b in inequalities:
paths = [a]
visited = {a}
while len(paths) > 0:
curr = paths.pop()
for j in equalGraph.get(curr, []):
if j not in visited:
paths.append(j)
if b in visited:
return False
return True
``````