1#include <iostream>
2#include <vector>
3#include <string>
4using namespace std;
5
6vector<int> parent;
7
8int find(int x) {
9    if (parent[x] != x) parent[x] = find(parent[x]);
10    return parent[x];
11}
12
13void union_set(int x, int y) {
14    int rootX = find(x);
15    int rootY = find(y);
16    if (rootX != rootY) parent[rootY] = rootX;
17}
18
19bool areSimilar(string a, string b) {
20    int diff = 0;
21    for (int i = 0; i < a.length(); ++i) {
22        if (a[i] != b[i]) {
23            diff++;
24            if (diff > 2) return false;
25        }
26    }
27    return diff == 2 || diff == 0;
28}
29
30int numSimilarGroups(vector<string>& strs) {
31    int n = strs.size();
32    parent.resize(n);
33    for (int i = 0; i < n; ++i) parent[i] = i;
34
35    for (int i = 0; i < n; ++i) {
36        for (int j = i + 1; j < n; ++j) {
37            if (areSimilar(strs[i], strs[j])) {
38                union_set(i, j);
39            }
40        }
41    }
42
43    int count = 0;
44    for (int i = 0; i < n; ++i) {
45        if (find(i) == i) {
46            count++;
47        }
48    }
49    return count;
50}
51
52int main() {
53    vector<string> strs = {"tars", "rats", "arts", "star"};
54    cout << numSimilarGroups(strs) << endl;
55    return 0;
56}
57

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