839. Similar String Groups

One tip is that all words are guaranteed to be anagrams so simply count diff characters will ensure similar words
Version #2 DFS
The hash set can help to skip same string

 24.32 %
class Solution {
    public int numSimilarGroups(String[] A) {
Set<String> visited = new HashSet<>();
int count = 0;
for (int i = 0; i < A.length; i++) {
if (!visited.contains(A[i])) {
dfs(i, A, visited);
                count++;
}
}
return count;
}

private void dfs(int curr, String[] A, Set<String> visited) {
visited.add(A[curr]);
for (int next = 0; next < A.length; next++) {
if (!visited.contains(A[next]) && isSimilar(A[curr], A[next])) {
dfs(next, A, visited);
}
}
}

private boolean isSimilar(String a, String b) {
int diff = 0;
for (int i = 0; i < a.length(); i++) {
if (a.charAt(i) != b.charAt(i)) {
diff++;
}
}
return diff == 2;
}
}


Version #1 Classical Union Find
1 bug is if two string are same, they are still similar

36.07 %
class Solution {
    int[] id;
int[] size;
int count;
public int numSimilarGroups(String[] A) {
id = new int[A.length];
size = new int[A.length];
count = A.length;
for (int i = 0; i < A.length; i++) {
id[i] = i;
size[i] = 1;
}
// unvisited set
Set<Integer> ids = new HashSet<>();
for (int i = 0; i < A.length; i++) {
ids.add(i);
}
for (int i = 0; i < A.length; i++) {
if (!ids.contains(i)) {
continue;
}
ids.remove(i);
for (int id : ids) {
if (isConnected(A[i], A[id])) {
union(i, id);
}
}
}
return count;
}

private int root(int i) {
while(id[i] != i) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}

private void union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
if (rootP == rootQ) {
return;
}
if (size[rootP] < size[rootQ]) {
id[rootP] = rootQ;
size[rootQ] += size[rootP];
} else {
id[rootQ] = rootP;
size[rootP] += size[rootQ];
}
count--;
}

private boolean isConnected(String a, String b) {
Integer i1 = null;
Integer i2 = null;
for (int i = 0; i < a.length(); i++) {
if (a.charAt(i) != b.charAt(i)) {
if (i1 == null) {
i1 = i;
} else if (i2 == null) {
i2 = i;
} else {
return false;
}
}
}
        if (i1 == null) {
return i2 == null;
}
return a.charAt(i1) == b.charAt(i2) && a.charAt(i2) == b.charAt(i1);
}
}