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
60
61
62
63
64
65
66
67
|
// 2416. Sum of Prefix Scores of Strings
#include "leetcode.h"
/*
* you are given an array 'words' of size 'n' consisting of non empty strings.
* we define the score of a string 'word' as the number of strings 'words[i]'
* such that 'word' is a prefix of 'words[i]'. return an array 'answer' of size
* 'n' where 'answer[i]' is the sum of the scores of every non empty prefix of
* 'words[i]'. note that a string is considered as a prefix of itself.
*/
struct trie {
struct trie *children[26];
int cnt;
};
struct trie *trie_init() {
return (struct trie *)calloc(sizeof(struct trie), 1);
}
int trie_insert(struct trie *obj, char *word) {
int n = strlen(word), idx;
for (int i = 0; i < n; i++) {
idx = word[i] - 'a';
if (!obj->children[idx])
obj->children[idx] = trie_init();
obj->children[idx]->cnt++;
obj = obj->children[idx];
}
return n;
}
int trie_pre_cnt(struct trie *obj, char *word) {
int n = strlen(word), res = 0, idx;
for (int i = 0; i < n; i++) {
idx = word[i] - 'a';
res += obj->children[idx]->cnt;
obj = obj->children[idx];
}
return res;
}
int *sumPrefixScores(char **words, int wordsSize, int *returnSize) {
struct trie *t = trie_init();
int max_len = INT_MIN;
for (int i = 0; i < wordsSize; i++)
max_len = fmax(max_len, trie_insert(t, words[i]));
int *ans = (int *)calloc(sizeof(int), max_len + 1);
*returnSize = 0;
for (int i = 0; i < wordsSize; i++)
ans[(*returnSize)++] = trie_pre_cnt(t, words[i]);
return ans;
}
int main() {
int rs1, rs2;
char *w1[] = {"abc", "ab", "bc", "b"}, *w2[] = {"abcd"};
int *sps1 = sumPrefixScores((char **)w1, ARRAY_SIZE(w1), &rs1);
int *sps2 = sumPrefixScores((char **)w2, ARRAY_SIZE(w2), &rs2);
for (int i = 0; i < rs1; i++)
printf("%d ", sps1[i]); // expect: 5 4 3 2
printf("\n");
for (int i = 0; i < rs2; i++)
printf("%d ", sps2[i]); // expect: 4
printf("\n");
free(sps1), free(sps2);
}
|