- Problem

839. Similar String Groups

- 내 코드 (Union-find)

class Solution:
    def numSimilarGroups(self, strs: List[str]) -> int:
        def find(x):
            if x != parents[x]:
                parents[x] = find(parents[x])
            return parents[x]
            
        def union(x, y):
            parents[find(x)] = find(y)

        def is_similar_string(s1, s2):
            return sum(c1 != c2 for c1, c2 in zip(s1, s2)) in [0, 2]

        parents = {s: s for s in strs}

        for i in range(len(strs)):
            for j in range(i+1, len(strs)):
                if is_similar_string(strs[i], strs[j]):
                    union(strs[i], strs[j])

        return len({find(s) for s in strs})

- 결과