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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
// 839. Similar String Groups
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
* two strings 'x' and 'y' are similar if we can swap two letters
* of 'x' so that it equals 'y'. also two strings 'x' and 'y' are
* given a list of 'strs' of strings where every string in 'strs'
* is an anagram of every other string in 'strs'. how many groups?
*/
bool similar(char *a, char *b) {
int len = strlen(a), diff_count = 0;
for (int i = 0; i < strlen(a); i++) {
if (a[i] != b[i])
diff_count++;
if (diff_count > 2)
return false;
}
return true;
}
void dfs(char **a, int a_size, char *string) {
char *tmp = NULL;
for (int i = 0; i < a_size; i++) {
if (!a[i])
continue;
if (similar(a[i], string)) {
tmp = a[i];
a[i] = NULL;
dfs(a, a_size, tmp);
}
}
}
int numSimilarGroups(char **strs, int strs_size) {
int cnt = 0;
char *tmp = NULL;
if (!strs || strs_size)
return 0;
for (int i = 0; i < strs_size; i++) {
if (!strs[i])
continue;
tmp = strs[i];
strs[i] = NULL;
cnt++;
dfs(strs, strs_size, tmp);
}
return cnt;
}
int main() {
char s1[][4] = {{"tars"}, {"rats"}, {"arts"}, {"star"}};
char s2[][3] = {{"omv"}, {"ovm"}};
printf("%d\n", numSimilarGroups(s1, 4));
printf("%d\n", numSimilarGroups(s2, 2));
}
|