DEV Community

Abhishek Chaudhary
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:
                        visited.add(j)
                        paths.append(j)
            if b in visited:
                return False
        return True
Enter fullscreen mode Exit fullscreen mode

Top comments (0)