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.
1class TrieNode:
2 def __init__(self):
3 self.children = {}
4 self.count = 0
5
6class Trie:
7 def __init__(self):
8 self.root = TrieNode()
9
10 def insert(self, word):
11 node = self.root
12 for char in word:
13 if char not in node.children:
14 node.children[char] = TrieNode()
15 node = node.children[char]
16 node.count += 1
17
18 def calculate_prefix_score(self, word):
19 node = self.root
20 score = 0
21 for char in word:
22 node = node.children[char]
23 score += node.count
24 return score
25
26def sum_of_prefix_scores(words):
27 trie = Trie()
28 for word in words:
29 trie.insert(word)
30 return [trie.calculate_prefix_score(word) for word in words]
31
32words = ["abc", "ab", "bc", "b"]
33print(sum_of_prefix_scores(words))The Python solution initializes a Trie to hold the words, incrementing the count at each node during insertion. To determine prefix scores, we walk along the Trie and sum up the node counts collected along the way.
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.
1function sumOfPrefixScores(words) {
2 const prefixCount = {};
3 for (const word of words) {
4 let prefix = '';
5 for (const char of word) {
6 prefix += char;
7 if (prefixCount[prefix] == undefined) {
8 prefixCount[prefix] = 0;
9 }
10 prefixCount[prefix]++;
11 }
12 }
13 return words.map(word => {
14 let prefix = '';
15 let score = 0;
16 for (const char of word) {
17 prefix += char;
18 score += prefixCount[prefix];
19 }
20 return score;
21 });
22}
23
24const words = ["abc", "ab", "bc", "b"];
25console.log(sumOfPrefixScores(words));Using JavaScript, prefix counts are managed within an object, built iteratively during iteration over words. For computing prefix scores, it harnesses pre-accumulated values inside the dictionary for effective compilation.