🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏
\n\n\n---\n\n## Intuition\nThe task involves calculating the "prefix score" for each word in a list, where the prefix score is the sum of the counts of all pref
![image.png](https://assets.leetcode.com/users/images/efd10c26-468e-41a6-8e7b-2772a09c8cea_1727243131.880963.png)\n\n\n---\n\n## Intuition\nThe task involves calculating the "prefix score" for each word in a list, where the prefix score is the sum of the counts of all prefixes of the word in the given word list. The Trie data structure is well-suited for such prefix-based queries, as it allows efficient insertion of words and tracking of prefix counts.\n\n---\n\n## Approach\n1. **Trie Construction**: Insert each word into the Trie, and at each node, maintain a count of how many times a prefix has been encountered.\n2. **Score Calculation**: For each word, traverse through the Trie and sum up the counts at each node corresponding to the prefixes of the word.\n3. **Efficiency**: The Trie allows us to efficiently handle prefix operations for all words, reducing the complexity of calculating prefix scores compared to a brute force approach.\n\n---\n\n## Complexity\n- **Time complexity**:  \n  - Insertion of a word into the Trie takes $$O(L)$$, where $$L$$ is the length of the word.  \n  - Calculating the score for a word also takes $$O(L)$$.\n  - For a list of $$n$$ words with an average length of $$L$$, the time complexity is $$O(n \\times L)$$.\n\n- **Space complexity**:  \n  - The space complexity is $$O(n \\times L)$$ for storing the Trie, where $$n$$ is the number of words and $$L$$ is the average word length.\n\n---\n## Code Implementations\n\n\n```dart []\nclass TrieNode {\n  Map<String, TrieNode> children = {};\n  int count = 0;\n}\n\nclass Trie {\n  TrieNode root = TrieNode();\n  \n  // Function to insert a word into the trie and update prefix counts\n  void insert(String word) {\n    TrieNode node = root;\n    for (int i = 0; i < word.length; i++) {\n      String char = word[i];\n      if (!node.children.containsKey(char)) {\n        node.children[char] = TrieNode();\n      }\n      node = node.children[char]!;\n      node.count++; // Update count for this prefix\n    }\n  }\n\n  // Function to calculate the score for a word\n  int calculateScore(String word) {\n    TrieNode node = root;\n    int score = 0;\n    for (int i = 0; i < word.length; i++) {\n      String char = word[i];\n      node = node.children[char]!;\n      score += node.count; // Add the count for each prefix\n    }\n    return score;\n  }\n}\n\nclass Solution {\n  List<int> sumPrefixScores(List<String> words) {\n    Trie trie = Trie();\n    \n    // Step 1: Insert all words into the Trie\n    for (String word in words) {\n      trie.insert(word);\n    }\n    \n    // Step 2: Calculate the score for each word\n    List<int> result = [];\n    for (String word in words) {\n      result.add(trie.calculateScore(word));\n    }\n    \n    return result;\n  }\n}\n```\n\n\n\n```java []\nimport java.util.HashMap;\nimport java.util.Map;\n\nclass TrieNode {\n    Map<Character, TrieNode> children = new HashMap<>();\n    int count = 0;\n}\n\nclass Trie {\n    TrieNode root = new TrieNode();\n\n    public void insert(String word) {\n        TrieNode node = root;\n        for (char ch : word.toCharArray()) {\n            node.children.putIfAbsent(ch, new TrieNode());\n            node = node.children.get(ch);\n            node.count++;\n        }\n    }\n\n    public int calculateScore(String word) {\n        TrieNode node = root;\n        int score = 0;\n        for (char ch : word.toCharArray()) {\n            node = node.children.get(ch);\n            score += node.count;\n        }\n        return score;\n    }\n}\n\nclass Solution {\n    public int[] sumPrefixScores(String[] words) {\n        Trie trie = new Trie();\n\n        // Step 1: Insert all words into the Trie\n        for (String word : words) {\n            trie.insert(word);\n        }\n\n        // Step 2: Calculate the score for each word\n        int[] result = new int[words.length];\n        for (int i = 0; i < words.length; i++) {\n            result[i] = trie.calculateScore(words[i]);\n        }\n        return result;\n    }\n}\n```\n\n\n\n```javascript []\nclass TrieNode {\n    constructor() {\n        this.children = new Map();\n        this.count = 0;\n    }\n}\n\nclass Trie {\n    constructor() {\n        this.root = new TrieNode();\n    }\n\n    insert(word) {\n        let node = this.root;\n        for (const char of word) {\n            if (!node.children.has(char)) {\n                node.children.set(char, new TrieNode());\n            }\n            node = node.children.get(char);\n            node.count++;\n        }\n    }\n\n    calculateScore(word) {\n        let node = this.root;\n        let score = 0;\n        for (const char of word) {\n            node = node.children.get(char);\n            score += node.count;\n        }\n        return score;\n    }\n}\n\nfunction sumPrefixScores(words) {\n    const trie = new Trie();\n\n    // Step 1: Insert all words into the Trie\n    for (const word of words) {\n        trie.insert(word);\n    }\n\n    // Step 2: Calculate the score for each word\n    return words.map(word => trie.calculateScore(word));\n}\n```\n\n\n\n```python []\nclass TrieNode:\n    def __init__(self):\n        self.children = {}\n        self.count = 0\n\nclass Trie:\n    def __init__(self):\n        self.root = TrieNode()\n\n    def insert(self, word):\n        node = self.root\n        for ch in word:\n            if ch not in node.children:\n                node.children[ch] = TrieNode()\n            node = node.children[ch]\n            node.count += 1\n\n    def calculate_score(self, word):\n        node = self.root\n        score = 0\n        for ch in word:\n            node = node.children[ch]\n            score += node.count\n        return score\n\nclass Solution:\n    def sumPrefixScores(self, words):\n        trie = Trie()\n\n        # Step 1: Insert all words into the Trie\n        for word in words:\n            trie.insert(word)\n\n        # Step 2: Calculate the score for each word\n        return [trie.calculate_score(word) for word in words]\n```\n\n\n\n```cpp []\n#include <unordered_map>\n#include <vector>\n#include <string>\n\nusing namespace std;\n\nclass TrieNode {\npublic:\n    unordered_map<char, TrieNode*> children;\n    int count = 0;\n};\n\nclass Trie {\npublic:\n    TrieNode* root;\n    \n    Trie() {\n        root = new TrieNode();\n    }\n\n    void insert(const string& word) {\n        TrieNode* node = root;\n        for (char ch : word) {\n            if (node->children.find(ch) == node->children.end()) {\n                node->children[ch] = new TrieNode();\n            }\n            node = node->children[ch];\n            node->count++;\n        }\n    }\n\n    int calculateScore(const string& word) {\n        TrieNode* node = root;\n        int score = 0;\n        for (char ch : word) {\n            node = node->children[ch];\n            score += node->count;\n        }\n        return score;\n    }\n};\n\nclass Solution {\npublic:\n    vector<int> sumPrefixScores(vector<string>& words) {\n        Trie trie;\n        \n        // Step 1: Insert all words into the Trie\n        for (const string& word : words) {\n            trie.insert(word);\n        }\n        \n        // Step 2: Calculate the score for each word\n        vector<int> result;\n        for (const string& word : words) {\n            result.push_back(trie.calculateScore(word));\n        }\n        \n        return result;\n    }\n};\n```\n\n\n\n```c []\n#include <stdio.h>\n#include <stdlib.h>\n#include <string.h>\n\ntypedef struct TrieNode {\n    struct TrieNode* children[26];\n    int count;\n} TrieNode;\n\nTrieNode* createNode() {\n    TrieNode* node = (TrieNode*) malloc(sizeof(TrieNode));\n    for (int i = 0; i < 26; i++) {\n        node->children[i] = NULL;\n    }\n    node->count = 0;\n    return node;\n}\n\nvoid insert(TrieNode* root, const char* word) {\n    TrieNode* node = root;\n    for (int i = 0; word[i] != \'\\0\'; i++) {\n        int index = word[i] - \'a\';\n        if (node->children[index] == NULL) {\n            node->children[index] = createNode();\n        }\n        node = node->children[index];\n        node->count++;\n    }\n}\n\nint calculateScore(TrieNode* root, const char* word) {\n    TrieNode* node = root;\n    int score = 0;\n    for (int i = 0; word[i] != \'\\0\'; i++) {\n        int index = word[i] - \'a\';\n        node = node->children[index];\n        score += node->count;\n    }\n    return score;\n}\n\nint* sumPrefixScores(char** words, int wordsSize, int* returnSize) {\n    TrieNode* root = createNode();\n    int* result = (int*) malloc(wordsSize * sizeof(int));\n\n    // Step 1: Insert all words into the Trie\n    for (int i = \n\n0; i < wordsSize; i++) {\n        insert(root, words[i]);\n    }\n\n    // Step 2: Calculate the score for each word\n    for (int i = 0; i < wordsSize; i++) {\n        result[i] = calculateScore(root, words[i]);\n    }\n\n    *returnSize = wordsSize;\n    return result;\n}\n```\n\n\n\n```go []\npackage main\n\nimport "fmt"\n\ntype TrieNode struct {\n\tchildren map[rune]*TrieNode\n\tcount    int\n}\n\ntype Trie struct {\n\troot *TrieNode\n}\n\nfunc NewTrie() *Trie {\n\treturn &Trie{root: &TrieNode{children: make(map[rune]*TrieNode)}}\n}\n\nfunc (t *Trie) Insert(word string) {\n\tnode := t.root\n\tfor _, ch := range word {\n\t\tif _, found := node.children[ch]; !found {\n\t\t\tnode.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}\n\t\t}\n\t\tnode = node.children[ch]\n\t\tnode.count++\n\t}\n}\n\nfunc (t *Trie) CalculateScore(word string) int {\n\tnode := t.root\n\tscore := 0\n\tfor _, ch := range word {\n\t\tnode = node.children[ch]\n\t\tscore += node.count\n\t}\n\treturn score\n}\n\nfunc sumPrefixScores(words []string) []int {\n\ttrie := NewTrie()\n\n\t// Step 1: Insert all words into the Trie\n\tfor _, word := range words {\n\t\ttrie.Insert(word)\n\t}\n\n\t// Step 2: Calculate the score for each word\n\tresult := make([]int, len(words))\n\tfor i, word := range words {\n\t\tresult[i] = trie.CalculateScore(word)\n\t}\n\n\treturn result\n}\n\nfunc main() {\n\twords := []string{"abc", "ab", "a"}\n\tfmt.Println(sumPrefixScores(words)) // Output: [3, 2, 1]\n}\n```\n\n---\n\n![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style=\'width:250px\'}\n\n
['Trie', 'C', 'C++', 'Java', 'Go', 'Python3', 'JavaScript', 'Dart']