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
|
// 916. Word Subsets
#include "leetcode.h"
/*
* you are given two string arrays 'words1' and 'words2'. a string 'b' is a
* subset of string 'a' if every letter in 'b' occurs in 'a' including
* multiplicity. a string 'a' from 'words1' is universal if for every string 'b'
* in 'words2', 'b' is a subset of 'a'. return an array of all the universal
* strins in 'words1'. you may return the answer in any order.
*/
char **wordSubsets(char **words1, int words1Size, char **words2, int words2Size,
int *returnSize) {
int max_freq[26] = {0}, tmp_freq[26];
for (int i = 0; i < words2Size; ++i) {
memset(tmp_freq, 0, sizeof(tmp_freq));
for (int j = 0; words2[i][j] != '\0'; ++j)
tmp_freq[words2[i][j] - 'a']++;
for (int j = 0; j < 26; ++j)
max_freq[j] = fmax(max_freq[j], tmp_freq[j]);
}
char **ans = (char **)malloc(words1Size * sizeof(char *));
*returnSize = 0;
for (int i = 0; i < words1Size; ++i) {
memset(tmp_freq, 0, sizeof(tmp_freq));
for (int j = 0; words1[i][j] != '\0'; ++j)
tmp_freq[words1[i][j] - 'a']++;
bool universal = true;
for (int j = 0; j < 26; ++j)
if (max_freq[j] > tmp_freq[j]) {
universal = false;
break;
}
if (universal)
ans[(*returnSize)++] = words1[i];
}
return ans;
}
int main() {
char *w11[] = {"amazon", "apple", "facebook", "google", "leetcode"},
*w21[] = {"e", "o"};
char *w12[] = {"amazon", "apple", "facebook", "google", "leetcode"},
*w22[] = {"l", "e"};
int rs1, rs2;
char **ws1 = wordSubsets((char **)w11, ARRAY_SIZE(w11), (char **)w21,
ARRAY_SIZE(w21), &rs1);
char **ws2 = wordSubsets((char **)w12, ARRAY_SIZE(w12), (char **)w22,
ARRAY_SIZE(w22), &rs2);
for (int i = 0; i < rs1; i++)
printf("%s ", ws1[i]); // expect: ["facebook","google","leetcode"]
printf("\n");
for (int i = 0; i < rs2; i++)
printf("%s ", ws2[i]); // expect: ["apple","google","leetcode"]
printf("\n");
free(ws1), free(ws2);
}
|