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 constructor() {
3 this.children = {};
4 this.count = 0;
5 }
6}
7
8class Trie {
9 constructor() {
10 this.root = new TrieNode();
11 }
12
13 insert(word) {
14 let node = this.root;
15 for (let char of word) {
16 if (!node.children[char]) {
17 node.children[char] = new TrieNode();
18 }
19 node = node.children[char];
20 node.count++;
21 }
22 }
23
24 calculatePrefixScore(word) {
25 let node = this.root;
26 let score = 0;
27 for (let char of word) {
28 node = node.children[char];
29 score += node.count;
30 }
31 return score;
32 }
33}
34
35function sumOfPrefixScores(words) {
36 const trie = new Trie();
37 for (let word of words) {
38 trie.insert(word);
39 }
40 return words.map(word => trie.calculatePrefixScore(word));
41}
42
43const words = ["abc", "ab", "bc", "b"];
44console.log(sumOfPrefixScores(words));The JavaScript solution constructs a Trie for the input words, incrementing counters at relevant nodes as each word is inserted. For prefix score calculation, it traverses through the Trie nodes relevant to each word, summing up their maintained counts to form the final result.
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.
1def sum_of_prefix_scores(words):
2 prefix_count = {}
3 for word in words:
4 prefix = ''
5 for char in word:
6 prefix += char
7 if prefix in prefix_count:
8 prefix_count[prefix] += 1
9 else:
10 prefix_count[prefix] = 1
11 result = []
12 for word in words:
13 prefix = ''
14 count = 0
15 for char in word:
16 prefix += char
17 count += prefix_count.get(prefix, 0)
18 result.append(count)
19 return result
20
21words = ["abc", "ab", "bc", "b"]
22print(sum_of_prefix_scores(words))The Python approach makes use of a dictionary to maintain prefix counts. It iteratively processes each word to populate the dictionary, then sums the hit counts for each word's prefixes to determine respective scores.