2020-01-03 11:15:27
问题描述：
问题求解：
本题最开始看的时候有点没搞懂，看似直接使用并查集并不太合适。
实际可以直接使用dfs来做，只需要将所有属于同一类的给标记掉即可，这也提醒我以后这种聚类的问题如果无法直接使用并查集来做的话，可以尝试一下使用dfs，另外，最近发现dfs是真的大杀器，绝大多数的问题都可以使用dfs来暴力出一个结果。
public int numSimilarGroups(String[] A) {
int n = A.length;
if (n < 2) return n;
int res = 0;
for (int i = 0; i < n; i++) {
if (A[i] == null) continue;
res += 1;
String str = A[i];
A[i] = null;
dfs(A, str);
}
return res;
}
private void dfs(String[] A, String str) {
for (int i = 0; i < A.length; i++) {
if (A[i] == null) continue;
if (helper(A[i], str)) {
String tmp = A[i];
A[i] = null;
dfs(A, tmp);
}
}
}
private boolean helper(String s1, String s2) {
int res = 0;
int[] count = new int[128];
boolean flag = false;
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) != s2.charAt(i)) res += 1;
if (res > 2) break;
count[s1.charAt(i)] += 1;
if (count[s1.charAt(i)] > 1) flag = true;
}
return res == 2 || (res == 0 && flag);
}
原文：https://www.cnblogs.com/hyserendipity/p/12143947.html