1
# Runtime: 5068 ms (Top 15.23%) | Memory: 14.3 MB (Top 64.62%)
2
class Solution:  # 839. Similar String Groups
3
    def numSimilarGroups(self, strs: List[str]) -> int:
4
        # memo
5
        visited = set()
6
        count = 0
7
        for i in range(len(strs)):
8
            if i not in visited:
9
                # dfs
10
                self.dfs(strs, i, visited)
11
                # add a new connected area
12
                count += 1
13
        return count
14

15
    # dfs to search the similar string from 0 to n-1
16
    def dfs(self, strs, i, visited):
17
        # add current string to memo
18
        visited.add(i)
19
        for j in range(len(strs)):
20
            if self.isSimilar(strs[i], strs[j]) and j not in visited:
21
                self.dfs(strs, j, visited)
22

23
    # calculate the similarity of two strings
24
    def isSimilar(self, str1, str2):
25
        diff_count = 0
26
        for i in range(len(str1)):
27
            if str1[i] != str2[i]:
28
                diff_count += 1
29
        return diff_count <= 2