Участник:Timatizak/similarstringgroups

Материал из DISCOPAL
Перейти к: навигация, поиск
class Solution:
    def numSimilarGroups(self, A: List[str]) -> int:
        def similar(w1, w2):
            return sum(w1[i] != w2[i] for i in range(len(w1))) == 2
 
        def swap(word, i, j):
            return word[:i] + word[j] + word[i+1:j] + word[i] + word[j+1:]
 
        m, n = len(A[0]), len(A)
        words = set(A)
        visited = set()
 
        def dfs(word):
            visited.add(word)
 
            if m < n:
                for i in range(m):
                    for j in range(i + 1, m):
                        swapped = swap(word, i, j)
                        if swapped in words and swapped not in visited:
                            dfs(swapped)
            else:
                for word1 in A:
                    if word1 not in visited and similar(word, word1):
                        dfs(word1)
 
        res = 0
        for word in A:
            if word not in visited:
                dfs(word)
                res += 1
        return res