Problem statement

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

Solution

First we need to traverse and create connected components for == conditions. Then we need to traverse once again and check that we do not have != between different components. We can use union find here or usual dfs.

Complexity

It is O(n), where n is number of equations.

Code

class DSU:
    def __init__(self, N):
        self.p = list(range(N))

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        self.p[xr] = yr

class Solution:
    def equationsPossible(self, equations):
        dsu = DSU(26)
        for eq in equations:
            if eq[1] == "=":
                dsu.union(ord(eq[0]) - 97, ord(eq[3]) - 97)
        
        for eq in equations:
            if eq[1] == "!":
                if dsu.find(ord(eq[0]) - 97) == dsu.find(ord(eq[3]) - 97):
                    return False
                
        return True