题目
如果交换字符串X中的两个字符就能得到字符串Y，那么两个字符串X和Y相似。例如，字符串"tars"和"rats"相似（交换下标为0和2的两个字符）、字符串"rats"和"arts"相似（交换下标为0和1的字符），但字符串"star"和"tars"不相似。
输入一个字符串数组，根据字符串的相似性分组，请问能把输入数组分成几组？如果一个字符串至少和一组字符串中的一个相似，那么它就可以放到该组中。假设输入数组中的所有字符串的长度相同并且两两互为变位词。例如，输入数组为[“tars”，“rats”，“arts”，“star”]，可以分成两组，一组为{“tars”，“rats”，“arts”}，另一组为{“star”}。
分析
把输入数组中的每个字符串看成图中的一个节点。如果两个字符串相似，那么它们对应的节点之间有一条边相连，也就属于同一个子图。例如，字符串[“tars”，“rats”，“arts”，“star”]根据相似性分别属于两个子图
解
public class Test {
public static void main(String[] args) {
String[] A = {
"tars", "rats", "arts", "star"};
int result = numSimilarGroups(A);
System.out.println(result);
}
public static int numSimilarGroups(String[] A) {
int[] fathers = new int[A.length];
for (int i = 0; i < fathers.length; i++) {
fathers[i] = i;
}
int groups = A.length;
for (int i = 0; i < A.length; i++) {
for (int j = i + 1; j < A.length; j++) {
if (similar(A[i], A[j]) && union(fathers, i, j)) {
groups--;
}
}
}
return groups;
}
private static boolean similar(String str1, String str2) {
int diffCount = 0;
for (int i = 0; i < str1.length(); i++) {
if (str1.charAt(i) != str2.charAt(i)) {
diffCount++;
}
}
return diffCount <= 2;
}
private static boolean union(int[] fathers, int i, int j) {
int fatherOfI = findFather(fathers, i);
int fatherOfJ = findFather(fathers, j);
if (fatherOfI != fatherOfJ) {
fathers[fatherOfI] = fatherOfJ;
return true;
}
return false;
}
private static int findFather(int[] fathers, int i) {
if (fathers[i] != i) {
fathers[i] = findFather(fathers, fathers[i]);
}
return fathers[i];
}
}
