Similar String Groups

Intuition

Solution

class Solution:
    def similar(self, A, i, j):
        diff = 0
        for c1, c2 in zip(A[i], A[j]):
            if c1 != c2:
                diff += 1
                if diff > 2:
                    return False
        return True

    def numSimilarGroups(self, A: List[str]) -> int:
        A = list(set(A))
        if not A:
            return 0
        W = len(A[0])
        N = len(A)

        dsu = DSU(N)
        if N < W * W:
            for i in range(N):
                for j in range(i + 1, N):
                    if self.similar(A, i, j):
                        dsu.union(i, j)
        else:
            indexes = {c: i for i, c in enumerate(A)}
            for i, w in enumerate(A):
                for p in range(W):
                    for q in range(p + 1, W):
                        tmp = w[:p] + w[q] + w[p + 1:q] + w[p] + w[q + 1:]
                        if tmp in indexes:
                            j = indexes[tmp]
                            dsu.union(i, j)

        return dsu.count()