1
class Solution {
2
 public:
3
  bool similar(string &s, string &t) {
4
    int dif = 0;
5
    for (int i = 0; i < s.size(); i++) {
6
      if (s[i] != t[i]) {
7
        dif++;
8
      }
9
    }
10
    return dif <= 2;
11
  }
12
  void dfs(int node, vector<int> &vis, vector<vector<int>> &graph) {
13
    vis[node] = 1;
14
    for (auto &child : graph[node]) {
15
      if (!vis[child]) {
16
        dfs(child, vis, graph);
17
      }
18
    }
19
  }
20
  int numSimilarGroups(vector<string> &strs) {
21
    int n = strs.size();
22
    vector<vector<int>> graph(strs.size());
23
    for (int i = 1; i < n; i++) {
24
      for (int j = 0; j < i; j++) {
25
        if (similar(strs[i], strs[j])) {
26
          graph[i].push_back(j);
27
          graph[j].push_back(i);
28
        }
29
      }
30
    }
31
    int ans = 0;
32
    vector<int> vis(n);
33
    for (int i = 0; i < n; i++) {
34
      if (!vis[i]) {
35
        dfs(i, vis, graph);
36
        ans++;
37
      }
38
    }
39
    return ans;
40
  }
41
};