# 2416. Sum of Prefix Scores of Strings

• Time: $O(\Sigma |\texttt{words[i]}|)$
• Space: $O(\Sigma |\texttt{words[i]}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 struct TrieNode { vector> children; int count = 0; TrieNode() : children(26) {} }; class Solution { public: vector sumPrefixScores(vector& words) { vector ans; for (const string& word : words) insert(word); for (const string& word : words) ans.push_back(getScore(word)); return ans; } private: shared_ptr root = make_shared(); void insert(const string& word) { shared_ptr node = root; for (const char c : word) { const int i = c - 'a'; if (node->children[i] == nullptr) node->children[i] = make_shared(); node = node->children[i]; ++node->count; } } int getScore(const string& word) { shared_ptr node = root; int score = 0; for (const char c : word) { node = node->children[c - 'a']; score += node->count; } return score; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class TrieNode { public TrieNode[] children = new TrieNode[26]; public int count = 0; } class Solution { public int[] sumPrefixScores(String[] words) { int[] ans = new int[words.length]; for (final String word : words) insert(word); for (int i = 0; i < words.length; ++i) ans[i] = getScore(words[i]); return ans; } private TrieNode root = new TrieNode(); private void insert(String word) { TrieNode node = root; for (final char c : word.toCharArray()) { final int i = c - 'a'; if (node.children[i] == null) node.children[i] = new TrieNode(); node = node.children[i]; ++node.count; } } private int getScore(String word) { TrieNode node = root; int score = 0; for (final char c : word.toCharArray()) { node = node.children[c - 'a']; score += node.count; } return score; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class TrieNode: def __init__(self): self.children: Dict[str, TrieNode] = {} self.count = 0 class Solution: def sumPrefixScores(self, words: List[str]) -> List[int]: root = TrieNode() def insert(word: str) -> None: node: TrieNode = root for c in word: node = node.children.setdefault(c, TrieNode()) node.count += 1 for word in words: insert(word) def getScore(word: str) -> int: node: TrieNode = root score = 0 for c in word: node = node.children[c] score += node.count return score return [getScore(word) for word in words]