2023.04.28 Today's Challenge

fabichoi 2023. 4. 28. 23:45

https://leetcode.com/problems/similar-string-groups/

Similar String Groups - LeetCode

Can you solve this real interview question? Similar String Groups - Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y. Also two strings X and Y are similar if they are equal. For example, "tars

leetcode.com

Union-Find 기법 사용.
소스가 좀 긴 편이다.

class Solution:
    def numSimilarGroups(self, strs: List[str]) -> int:
        UF = {}
        ranks = defaultdict(int)

        def find(x):
            if x not in UF:
                UF[x] = x
            if x != UF[x]:
                UF[x] = find(UF[x])
            return UF[x]
        
        def union(x, y):
            rx, ry = find(x), find(y)
            if ranks[rx] < ranks[ry]:
                UF[rx] = ry
                return
            UF[ry] = rx
            if ranks[rx] == ranks[ry]:
                ranks[rx] += 1
            
        def are_nei(a, b):
            dif = 0
            for i in range(len(a)):
                if a[i] != b[i]:
                    dif += 1
            return dif == 0 or dif == 2
        
        for i in range(len(strs)):
            for j in range(i+1, len(strs)):
                if are_nei(strs[i], strs[j]):
                    union(strs[i], strs[j])
            
        return len(set([find(x) for x in strs]))