LeetCode Q 839 - Similar String Groups

Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y.

For example, “tars” and “rats” are similar (swapping at positions 0 and 2), and “rats” and “arts” are similar, but “star” is not similar to “tars”, “rats”, or “arts”.

Together, these form two connected groups by similarity: {“tars”, “rats”, “arts”} and {“star”}. Notice that “tars” and “arts” are in the same group even though they are not similar. Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.

We are given a list A of strings. Every string in A is an anagram of every other string in A. How many groups are there?

Example 1:
Input: ["tars","rats","arts","star"] ; Output: 2

Note:

A.length <= 2000
A[i].length <= 1000
A.length * A[i].length <= 20000
All words in A consist of lowercase letters only.
All words in A have the same length and are anagrams of each other.
The judging time limit has been increased for this question.

Solution

Solution 1: Disjoint Set / Union Find

Code:

class UnionFindSet {
	int[] parent;
	int count;
	public UnionFindSet (int size) {
		this.parent = new int[size];
		for (int i = 0; i < size; i++) 
			parent[i] = i;
	}
	
	public int find (int x) {
		if (parent[x] != x) parent[x] = find(parent[x]);
		return parent[x];
	}
	
	public void union (int x, int y) {
		int px = find(x), py = find(y);
		if (px != py) { parent[px] = py; count--; }
	}
}

public int numSimilarGroups(String[] A) {
	if (A == null || A.length <= 1) return A.length;
	
	UnionFindSet ufs = new UnionFindSet(A.length);
	ufs.count = A.length;
	
	Map<String, Integer> strToId = new HashMap<>();
	
	for (int i = 0; i < A.length; i++) {
		String word = A[i];
		strToId.putIfAbsent(word, i);
		for (String str: strToId.keySet()) {
			if (canGroup(str, word)) 
				ufs.union(strToId.get(str), i); 
		}
	}
	
	return ufs.count;
}

private boolean canGroup (String a, String b) {
	int res = 0, len = a.length();
	for (int i = 0; i < len; i++) 
		if (a.charAt(i) != b.charAt(i) && ++res > 2) 
			return false;
	return true;
}

Code: More concise code

public int numSimilarGroups(String[] A) {
	if (A == null || A.length <= 1) return A.length;
	
	UnionFindSet ufs = new UnionFindSet(A.length);
	ufs.count = A.length;
	
	for (int i = 0; i < A.length; i++) {
		for (int j = i + 1; j < A.length; j++) {
			if (canGroup(A[i], A[j]))
				ufs.union(i, j);
		}
	}
	
	return ufs.count;
}

Reprint policy