Leetcode 1032 Solution

This article provides solution to leetcode question 1032 (satisfiability-of-equality-equations)
Categories:
Tags:
Access this page by simply typing in "lcs 1032" in your browser address bar if you have bunnylol configured.

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

Solution

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

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

    def union(self, i, j):
        pi = self.find(i)
        pj = self.find(j)
        self.p[pi] = pj

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        fuset = FindUnionSet(26)

        for equation in equations:
            if '!' in equation:
                continue
            src = ord(equation[0]) - ord('a')
            dst = ord(equation[3]) - ord('a')
            fuset.union(src, dst)

        for equation in equations:
            if '!' not in equation:
                continue
            src = ord(equation[0]) - ord('a')
            dst = ord(equation[3]) - ord('a')

            if fuset.find(src) == fuset.find(dst):
                return False
        return True