diff options
Diffstat (limited to 'sum_prefix_score_string.c')
-rw-r--r-- | sum_prefix_score_string.c | 67 |
1 files changed, 67 insertions, 0 deletions
diff --git a/sum_prefix_score_string.c b/sum_prefix_score_string.c new file mode 100644 index 0000000..c1024cd --- /dev/null +++ b/sum_prefix_score_string.c @@ -0,0 +1,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); +} |