1def find(parent, x):
2    if parent[x] != x:
3        parent[x] = find(parent, parent[x])
4    return parent[x]
5
6
7def union(parent, x, y):
8    rootX = find(parent, x)
9    rootY = find(parent, y)
10    if rootX != rootY:
11        parent[rootY] = rootX
12
13
14def are_similar(a, b):
15    diff = 0
16    for i in range(len(a)):
17        if a[i] != b[i]:
18            diff += 1
19            if diff > 2:
20                return False
21    return diff == 2 or diff == 0
22
23
24def num_similar_groups(strs):
25    n = len(strs)
26    parent = list(range(n))
27
28    for i in range(n):
29        for j in range(i + 1, n):
30            if are_similar(strs[i], strs[j]):
31                union(parent, i, j)
32
33    return len(set(find(parent, i) for i in range(n)))
34
35
36# Example usage:
37strs = ["tars", "rats", "arts", "star"]
38print(num_similar_groups(strs))
39

1
class Solution {
    private bool AreSimilar(string a, string b) {
        int diff = 0;
        for (int i = 0; i < a.Length; i++) {
            if (a[i] != b[i]) {
                diff++;
                if (diff > 2) return false;
            }
        }
        return diff == 2 || diff == 0;
    }

    private void Dfs(string[] strs, bool[] visited, int idx) {
        visited[idx] = true;
        for (int i = 0; i < strs.Length; i++) {
            if (!visited[i] && AreSimilar(strs[idx], strs[i])) {
                Dfs(strs, visited, i);
            }
        }
    }

    public int NumSimilarGroups(string[] strs) {
        int n = strs.Length;
        bool[] visited = new bool[n];
        int count = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                Dfs(strs, visited, i);
                count++;
            }
        }
        return count;
    }

    static void Main() {
        Solution s = new Solution();
        string[] strs = {"tars", "rats", "arts", "star"};
        Console.WriteLine(s.NumSimilarGroups(strs));
    }
}