839. Similar String Groups (Hard)
https://leetcode.com/problems/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.
Solutions
class Solution {
// Keep track of visited elements and never work on them twice
Set<Integer> visited = new HashSet<>();
public int numSimilarGroups(String[] A) {
int len = A.length;
int ans = 0;
for (int i = 0; i < len; i++) {
if (visited.contains(i)) {
continue;
}
// Group all the words that similar wth A[i] in A and put them into visited set.
dfs(A, i);
ans++;
}
return ans;
}
private void dfs(String[] A, int id) {
if (visited.contains(A[id])) {
return;
}
visited.add(id);
for (int i = 0; i < A.length; i++) {
if (i == id || visited.contains(i)) {
continue;
}
if (similar(A[id], A[i])) {
dfs(A, i);
}
}
}
private boolean similar(String word1, String word2) {
int diff = 0;
// bit-to-bit comparision
for (int i = 0; i < word1.length(); ++i) {
if (word1.charAt(i) != word2.charAt(i)) {
diff++;
}
}
return diff <= 2;
}
}