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 <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5#define ALPHABET_SIZE 26
6
7struct TrieNode {
8 struct TrieNode* children[ALPHABET_SIZE];
9 int count; // Count of words sharing this prefix
10};
11
12struct TrieNode* getNode() {
13 struct TrieNode* pNode = (struct TrieNode*)malloc(sizeof(struct TrieNode));
14 pNode->count = 0;
15 for (int i = 0; i < ALPHABET_SIZE; i++)
16 pNode->children[i] = NULL;
17 return pNode;
18}
19
20void insert(struct TrieNode* root, const char* key) {
21 struct TrieNode* pCrawl = root;
22 while (*key) {
23 int index = *key - 'a';
24 if (!pCrawl->children[index])
25 pCrawl->children[index] = getNode();
26 pCrawl = pCrawl->children[index];
27 pCrawl->count++;
28 key++;
29 }
30}
31
32int calculatePrefixScore(struct TrieNode* root, const char* key) {
33 struct TrieNode* pCrawl = root;
34 int score = 0;
35 while (*key) {
36 int index = *key - 'a';
37 if (pCrawl->children[index]) {
38 pCrawl = pCrawl->children[index];
39 score += pCrawl->count;
40 }
41 key++;
42 }
43 return score;
44}
45
46void prefixScores(char* words[], int n, int* answer) {
47 struct TrieNode* root = getNode();
48 for (int i = 0; i < n; i++)
49 insert(root, words[i]);
50 for (int i = 0; i < n; i++)
51 answer[i] = calculatePrefixScore(root, words[i]);
52}
53
54int main() {
55 char* words[] = {"abc", "ab", "bc", "b"};
56 int n = sizeof(words) / sizeof(words[0]);
57 int answer[n];
58 prefixScores(words, n, answer);
59 for (int i = 0; i < n; i++)
60 printf("answer[%d] = %d\n", i, answer[i]);
61 return 0;
62}The solution builds a Trie from the list of given words. For each word, it inserts it into the Trie, incrementing the count of words at each node traversed. This helps track how many words share the same prefix. After building the Trie, it calculates the prefix score for each word by traversing its prefixes in the Trie and summing up the 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.
1using System;
2using System.Collections.Generic;
3
4class Solution {
5 public int[] SumOfPrefixScores(string[] words) {
6 Dictionary<string, int> prefixCount = new Dictionary<string, int>();
7 foreach (string word in words) {
8 string prefix = "";
9 foreach (char ch in word) {
10 prefix += ch;
11 if (!prefixCount.ContainsKey(prefix))
12 prefixCount[prefix] = 0;
13 prefixCount[prefix]++;
14 }
15 }
16 int[] result = new int[words.Length];
17 for (int i = 0; i < words.Length; i++) {
18 string prefix = "";
19 int sum = 0;
20 foreach (char ch in words[i]) {
21 prefix += ch;
22 sum += prefixCount[prefix];
23 }
24 result[i] = sum;
25 }
26 return result;
27 }
28
29 public static void Main() {
30 string[] words = {"abc", "ab", "bc", "b"};
31 int[] result = new Solution().SumOfPrefixScores(words);
32 Console.WriteLine(string.Join(" ", result));
33 }
34}In C#, a dictionary encodes prefix occurrences for input words. By fetching these from the dictionary during evaluation of prefix scores, the method efficiently sums counts for insights.