Depth-First Search
Breadth-First Search
Union Find
Array
Hash Table
String
Description
Two strings, X
and Y
, are considered similar if either they are identical or we can make them equivalent by swapping at most two letters (in distinct positions) within the string X
.
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 strs
of strings where every string in strs
is an anagram of every other string in strs
. How many groups are there?
Example 1:
Input: strs = ["tars","rats","arts","star"]
Output: 2
Example 2:
Input: strs = ["omv","ovm"]
Output: 1
Constraints:
1 <= strs.length <= 300
1 <= strs[i].length <= 300
strs[i]
consists of lowercase letters only.
All words in strs
have the same length and are anagrams of each other.
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14 class Solution :
def numSimilarGroups ( self , strs : List [ str ]) -> int :
def find ( x ):
if p [ x ] != x :
p [ x ] = find ( p [ x ])
return p [ x ]
n , l = len ( strs ), len ( strs [ 0 ])
p = list ( range ( n ))
for i in range ( n ):
for j in range ( i + 1 , n ):
if sum ( strs [ i ][ k ] != strs [ j ][ k ] for k in range ( l )) <= 2 :
p [ find ( i )] = find ( j )
return sum ( i == find ( i ) for i in range ( n ))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43 class Solution {
private int [] p ;
public int numSimilarGroups ( String [] strs ) {
int n = strs . length ;
p = new int [ n ] ;
for ( int i = 0 ; i < n ; ++ i ) {
p [ i ] = i ;
}
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j = i + 1 ; j < n ; ++ j ) {
if ( check ( strs [ i ] , strs [ j ] )) {
p [ find ( i ) ] = find ( j );
}
}
}
int res = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
if ( i == find ( i )) {
++ res ;
}
}
return res ;
}
private boolean check ( String a , String b ) {
int cnt = 0 ;
int n = a . length ();
for ( int i = 0 ; i < n ; ++ i ) {
if ( a . charAt ( i ) != b . charAt ( i )) {
++ cnt ;
}
}
return cnt <= 2 ;
}
private int find ( int x ) {
if ( p [ x ] != x ) {
p [ x ] = find ( p [ x ] );
}
return p [ x ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 class Solution {
public :
vector < int > p ;
int numSimilarGroups ( vector < string >& strs ) {
int n = strs . size ();
p . resize ( n );
for ( int i = 0 ; i < n ; ++ i ) p [ i ] = i ;
for ( int i = 0 ; i < n ; ++ i )
for ( int j = i + 1 ; j < n ; ++ j )
if ( check ( strs [ i ], strs [ j ]))
p [ find ( i )] = find ( j );
int ans = 0 ;
for ( int i = 0 ; i < n ; ++ i )
if ( i == find ( i ))
++ ans ;
return ans ;
}
bool check ( string a , string b ) {
int cnt = 0 ;
for ( int i = 0 ; i < a . size (); ++ i )
if ( a [ i ] != b [ i ])
++ cnt ;
return cnt <= 2 ;
}
int find ( int x ) {
if ( p [ x ] != x ) p [ x ] = find ( p [ x ]);
return p [ x ];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 func numSimilarGroups ( strs [] string ) int {
n := len ( strs )
p := make ([] int , n )
for i := range p {
p [ i ] = i
}
check := func ( a , b string ) bool {
cnt := 0
for i := range a {
if a [ i ] != b [ i ] {
cnt ++
}
}
return cnt <= 2
}
var find func ( x int ) int
find = func ( x int ) int {
if p [ x ] != x {
p [ x ] = find ( p [ x ])
}
return p [ x ]
}
for i := 0 ; i < n ; i ++ {
for j := i + 1 ; j < n ; j ++ {
if check ( strs [ i ], strs [ j ]) {
p [ find ( i )] = find ( j )
}
}
}
ans := 0
for i := 0 ; i < n ; i ++ {
if i == find ( i ) {
ans ++
}
}
return ans
}
GitHub