839 Similar String Groups
1. Question
Two stringsX
andY
are similar if we can swap two letters (in different positions) ofX
, so that it equalsY
.
For example,"tars"
and"rats"
are similar (swapping at positions0
and2
), 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 listA
of strings. Every string inA
is an anagram of every other string inA
. 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.
2. Implementation
(1) Union Find
思路: Union Find的思想比较直接,两个string只要是similar的就直接union.需要注意的是isSimilar()里,按题目要求应该是diff等于2属于similar,但为了避免输入数组中的相同string,我们把相同string也union在一起。
class Solution {
public int numSimilarGroups(String[] A) {
if (A.length <= 1) {
return A.length;
}
UnionFind uf = new UnionFind(A.length);
for (int i = 0; i < A.length - 1; i++) {
for (int j = i + 1; j < A.length; j++) {
if (isSimilar(A[i], A[j])) {
uf.union(i, j);
}
}
}
return uf.count;
}
public boolean isSimilar(String s1, String s2) {
if (s1.length() != s2.length()) {
return false;
}
int diff = 0;
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) != s2.charAt(i)) {
++diff;
}
}
return diff == 0 || diff == 2;
}
class UnionFind {
int[] parents;
int[] size;
int count;
public UnionFind(int n) {
parents = new int[n];
size = new int[n];
count = n;
for (int i = 0; i < n; i++) {
parents[i] = i;
size[i] = 1;
}
}
public int find(int id) {
while (id != parents[id]) {
id = parents[id];
}
return id;
}
public void union(int i, int j) {
int rootI = find(i);
int rootJ = find(j);
if (rootI == rootJ) return;
if (size[rootI] < size[rootJ]) {
parents[rootI] = rootJ;
size[rootJ] += size[rootI];
}
else {
parents[rootJ] = rootI;
size[rootI] += size[rootJ];
}
--count;
}
}
}
3. Time & Space Complexity
Union Find: 时间复杂度O(n^2 * L), 空间复杂度O(n^2)
Last updated
Was this helpful?