leetcode hard : Similar String Groups

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

Similar String Groups - LeetCode

 

similar check는 두 string을 비교해

1. 다른 글자가 2개거나

2. 0개면 (두 string이 같으면)

similar하다라고 판단하면 된다.

 

리스트를 순회하면서 similar한게 있으면 지워버리고

내가 지운 단어에 대해서도 recursive call로 dfs를 하면된다.

그럼 dfs 한번 호출할때마다 그 단어랑 엮인 단어들은 리스트에서 모두 없어질것이다.

 

class Solution:
    def numSimilarGroups(self, strs: List[str]) -> int:
        def isSimilar(w1, w2):
            c = 0
            for i in range(len(w1)):
                if w1[i] != w2[i]: c += 1
            return c == 2 or c == 0

        def dfs(word):
            for i in range(len(lst)):
                if not lst[i]: continue
                if isSimilar(word, lst[i]):
                    w = lst[i]
                    lst[i] = None
                    dfs(w)

        ans = 0
        lst = strs[:]
        for i in range(len(lst)):
            if lst[i]:
                ans += 1
                dfs(lst[i])

        return ans