1
class Solution {
2
  public int numSimilarGroups(String[] strs) {
3
    boolean[] visited = new boolean[strs.length]; // record the word that we checked
4
    int res = 0;
5
    for (int i = 0; i < strs.length; i++) {
6
      if (!visited[i]) {
7
        res++;
8
        dfs(strs, visited, i);
9
      }
10
    }
11
    return res;
12
  }
13

14
  void dfs(
15
      String[] strs, boolean[] visited, int index) { // explore all similar words we can explore
16
    visited[index] = true;
17
    String curr = strs[index];
18
    for (int i = 0; i < strs.length; i++) {
19
      if (!visited[i] && isSimilar(curr, strs[i])) {
20
        dfs(strs, visited, i);
21
      }
22
    }
23
  }
24

25
  boolean isSimilar(String a, String b) {
26
    int diff = 0;
27
    for (int i = 0; i < a.length(); i++) {
28
      if (a.charAt(i) != b.charAt(i)) {
29
        diff++;
30
        if (diff > 2) return false;
31
      }
32
    }
33
    return true;
34
  }
35
}