1import java.util.*;
2
3public class Solution {
4    private int find(int[] parent, int x) {
5        if (parent[x] != x) parent[x] = find(parent, parent[x]);
6        return parent[x];
7    }
8    
9    private void union(int[] parent, int x, int y) {
10        int rootX = find(parent, x);
11        int rootY = find(parent, y);
12        parent[rootY] = rootX;
13    }
14
15    private boolean areSimilar(String a, String b) {
16        int diff = 0;
17        for (int i = 0; i < a.length(); i++) {
18            if (a.charAt(i) != b.charAt(i)) {
19                diff++;
20                if (diff > 2) return false;
21            }
22        }
23        return diff == 2 || diff == 0;
24    }
25
26    public int numSimilarGroups(String[] strs) {
27        int n = strs.length;
28        int[] parent = new int[n];
29        for (int i = 0; i < n; i++) parent[i] = i;
30
31        for (int i = 0; i < n; i++) {
32            for (int j = i + 1; j < n; j++) {
33                if (areSimilar(strs[i], strs[j])) {
34                    union(parent, i, j);
35                }
36            }
37        }
38
39        int count = 0;
40        for (int i = 0; i < n; i++) {
41            if (find(parent, i) == i) count++;
42        }
43        return count;
44    }
45    
46    public static void main(String[] args) {
47        Solution s = new Solution();
48        String[] strs = {"tars", "rats", "arts", "star"};
49        System.out.println(s.numSimilarGroups(strs));
50    }
51}
52

1#include <vector>
#include <string>
using namespace std;

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;
}

void dfs(vector<string>& strs, vector<bool>& visited, int idx) {
    visited[idx] = true;
    for (int i = 0; i < strs.size(); ++i) {
        if (!visited[i] && areSimilar(strs[idx], strs[i])) {
            dfs(strs, visited, i);
        }
    }
}

int numSimilarGroups(vector<string>& strs) {
    int n = strs.size();
    vector<bool> visited(n, false);
    int count = 0;

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

int main() {
    vector<string> strs = {"tars", "rats", "arts", "star"};
    cout << numSimilarGroups(strs) << endl;
    return 0;
}