aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-09-24 21:27:56 -0600
committerJack Sangdahl <[email protected]>2024-09-24 21:27:56 -0600
commitc53c788fc24031c6185ebdd8f723895ee2c000da (patch)
tree9e345315f9fda85185585b2f936ca428b4c1e152
parent97fb1a16a79fea703c4abb77c0fef85b8827a37d (diff)
downloadleetcode-c53c788fc24031c6185ebdd8f723895ee2c000da.tar.gz
leetcode-c53c788fc24031c6185ebdd8f723895ee2c000da.zip
2416. sum of prefix scores of strings
-rw-r--r--sum_prefix_score_string.c67
-rw-r--r--sum_prefix_score_string.py46
2 files changed, 113 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);
+}
diff --git a/sum_prefix_score_string.py b/sum_prefix_score_string.py
new file mode 100644
index 0000000..8c0b4ab
--- /dev/null
+++ b/sum_prefix_score_string.py
@@ -0,0 +1,46 @@
+# 2416. Sum of Prefix Scores of Strings
+
+"""
+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.
+"""
+
+
+class Trie:
+ def __init__(self):
+ self.children = [None] * 26
+ self.cnt = 0
+
+
+class Solution(object):
+ def sumPrefixScores(self, words):
+ """
+ :type words: List[str]
+ :rtype: List[int]
+ """
+ trie, a, ans = Trie(), ord("a"), []
+ for w in words:
+ t = trie
+ for c in w:
+ c = ord(c) - a
+ if not t.children[c]:
+ t.children = Trie()
+ t.children[c].cnt += 1
+ t = t.children[c]
+ for w in words:
+ t, curr = trie, 0
+ for c in w:
+ c = ord(c) - a
+ curr += t.children[c].cnt
+ t = t.children[c]
+ ans.append(curr)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.sumPrefixScores(words=["abc", "ab", "bc", "b"]))
+ print(obj.sumPrefixScores(words=["abcd"]))