A Trie is an efficient tree-like data structure that allows efficient retrieval of a string's prefix scores. We start by inserting each word into the Trie, along with maintaining a count at each node to track how many words share that prefix. Then, for each word, we traverse its prefixes in the Trie to compute the prefix score by collecting the counts stored at each relevant node.
The time complexity is O(n * m) where n is the number of words and m is the maximum length of the words, due to Trie insertions and lookups. The space complexity is O(N * m), N being the total length of all words combined, as each character might lead to a node in the Trie.
1#include <iostream>
2#include <vector>
3#include <string>
4using namespace std;
5
6struct TrieNode {
7 TrieNode* children[26];
8 int count;
9 TrieNode() {
10 fill_n(children, 26, nullptr);
11 count = 0;
12 }
13};
14
15class Trie {
16 TrieNode* root;
17public:
18 Trie() { root = new TrieNode(); }
19 void insert(const string& word) {
20 TrieNode* node = root;
21 for (char ch : word) {
22 if (!node->children[ch - 'a'])
23 node->children[ch - 'a'] = new TrieNode();
24 node = node->children[ch - 'a'];
25 node->count++;
26 }
27 }
28 int calculatePrefixScore(const string& word) {
29 TrieNode* node = root;
30 int score = 0;
31 for (char ch : word) {
32 node = node->children[ch - 'a'];
33 score += node->count;
34 }
35 return score;
36 }
37};
38
39vector<int> sumOfPrefixScores(vector<string>& words) {
40 Trie trie;
41 for (const string& word : words)
42 trie.insert(word);
43 vector<int> answer;
44 for (const string& word : words)
45 answer.push_back(trie.calculatePrefixScore(word));
46 return answer;
47}
48
49int main() {
50 vector<string> words = {"abc", "ab", "bc", "b"};
51 vector<int> answer = sumOfPrefixScores(words);
52 for (int ans : answer)
53 cout << ans << " ";
54 cout << endl;
55 return 0;
56}The C++ solution follows a similar approach as described above. We define a Trie data structure and insert all words into it, incrementing the count at each node. After building the Trie, we compute the prefix score for each word by traversing its prefixes and accumulating their counts.
We can also use a hashtable (or dictionary) to count how often each prefix appears in the list of words. Iterate through each word and generate all its prefixes, updating their counts in the hashtable. Afterwards, compute the sum of counts for each full word by referencing its prefixes in the hashtable.
Time complexity is O(n * m) as we process each prefix per word insertion and retrieval. Space complexity is potentially O(N * m), accounting for hash table storage of prefixes.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5#define MAX_WORD_LENGTH 1000
6#define TABLE_SIZE 1000003
7
8typedef struct Node {
9 char *key;
10 int value;
11 struct Node *next;
12} Node;
13
14unsigned long hash(const char *str) {
15 unsigned long hash = 5381;
16 int c;
17 while ((c = *str++))
18 hash = ((hash << 5) + hash) + c;
19 return hash;
20}
21
22void insert(Node **table, const char *key) {
23 unsigned long index = hash(key) % TABLE_SIZE;
24 Node *entry = table[index];
25 while (entry != NULL) {
26 if (strcmp(entry->key, key) == 0) {
27 entry->value += 1;
28 return;
29 }
30 entry = entry->next;
31 }
32 Node *new_node = malloc(sizeof(Node));
33 new_node->key = strdup(key);
34 new_node->value = 1;
35 new_node->next = table[index];
36 table[index] = new_node;
37}
38
39int get(Node **table, const char *key) {
40 unsigned long index = hash(key) % TABLE_SIZE;
41 Node *entry = table[index];
42 while (entry != NULL) {
43 if (strcmp(entry->key, key) == 0)
44 return entry->value;
45 entry = entry->next;
46 }
47 return 0;
48}
49
50void prefixScores(char *words[], int n, int *answer) {
51 Node *table[TABLE_SIZE] = {NULL};
52 char prefix[MAX_WORD_LENGTH];
53 for (int i = 0; i < n; i++) {
54 strcpy(prefix, "");
55 for (int j = 0; words[i][j] != '\0'; j++) {
56 prefix[j] = words[i][j];
57 prefix[j + 1] = '\0';
58 insert(table, prefix);
59 }
60 }
61 for (int i = 0; i < n; i++) {
62 strcpy(prefix, "");
63 answer[i] = 0;
64 for (int j = 0; words[i][j] != '\0'; j++) {
65 prefix[j] = words[i][j];
66 prefix[j + 1] = '\0';
67 answer[i] += get(table, prefix);
68 }
69 }
70}
71
72int main() {
73 char *words[] = {"abc", "ab", "bc", "b"};
74 int n = sizeof(words) / sizeof(words[0]);
75 int answer[n];
76 prefixScores(words, n, answer);
77 for (int i = 0; i < n; i++)
78 printf("answer[%d] = %d\n", i, answer[i]);
79 return 0;
80}The C solution uses a hash table to keep track of prefix counts. For every word, we insert each of its prefixes into the hash table, updating their counts. Then, by iterating over prefixes of each word and retrieving their counts from the hash table, it calculates the prefix scores.