839. Similar String Groups - cocoder39/coco39_LC GitHub Wiki

839. Similar String Groups

class UnionFind:
    def __init__(self):
        self.parents = {}
        self.sizes = {}
        self.count = 0
    
    def findRoot(self, val):
        while val != self.parents[val]:
            val = self.parents[self.parents[val]]
        return val
    
    def add(self, val):
        if val not in self.parents:
            self.parents[val] = val
            self.sizes[val] = 1
            self.count += 1
    
    def union(self, val1, val2):
        root1 = self.findRoot(val1)
        root2 = self.findRoot(val2)
        if root1 != root2:
            size1, size2 = self.sizes[root1], self.sizes[root2]
            if size1 < size2:
                self.parents[root1] = root2
                self.sizes[root2] = size1 + size2
            else:
                self.parents[root2] = root1
                self.sizes[root1] = size1 + size2
            self.count -= 1

class Solution:
    def numSimilarGroups(self, strs: List[str]) -> int:
        uf = UnionFind()
        for val in strs:
            uf.add(val)
        
        n = len(strs)
        for i in range(n):
            for j in range(i+1, n):
                if self.isSimilar(strs[i], strs[j]):
                    uf.union(strs[i], strs[j])
        
        return uf.count
    
    
    def isSimilar(self, str1: str, str2: str) -> bool:
        l = len(str1)
        count = 0
        for i in range(l):
            if str1[i] != str2[i]:
                count += 1
            if count > 2:
                return False
        
        return count == 2