Simple step by step solution using Trie data structure
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem can be effectively solved using a Trie (prefix tree) data structure. The Tr
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem can be effectively solved using a Trie (prefix tree) data structure. The Trie structure allows us to efficiently store and traverse the prefixes of words. Each node in the Trie keeps track of how many times a particular prefix has appeared. This enables us to calculate the prefix scores for each word by summing the count of nodes that match the word\'s prefix.\n\nThe main idea is to:\n\n1. **Insert each word** into the Trie, where each node tracks how many times a prefix has been encountered.\n1. **Query the prefix** score of each word by summing the prefix counts while traversing the Trie.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Trie Construction:\n\n    - Each node of the Trie contains a count (to store the number of words that pass through this node) and an array to hold child nodes corresponding to each character (a-z).\n    - When inserting a word, for each character in the word:\n        - If the node for the character doesn\u2019t exist, create it.\n        - Increment the count for the node to indicate that a word has passed through this node.\n1. Prefix Score Calculation:\n\n    - To calculate the prefix score for a word, traverse the Trie for each character in the word.\n    - At each step, add the count of the node to the result, which will give the total number of words that share the prefix.\n1. Efficiency:\n\n    - Insertion and prefix calculation are both O(L) operations, where L is the length of the word. This ensures efficient processing even for larger input sizes.\n1. **Steps:**\n    - Insert all words into the Trie:\nFor each word in the input list, add it to the Trie, updating the count of each node.\n    - Calculate the prefix scores:\nFor each word, traverse the Trie and sum the counts of the nodes along the way to calculate the total prefix score for that word.\n\n# Complexity\n- Time complexity:O(N*W)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(N*W)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n```java []\nclass Node {\n    int count = 0;\n    Node[] list = new Node[26];\n\n    public boolean containKey(char ch) {\n        return list[ch - \'a\'] != null;\n    }\n\n    public Node get(char ch) {\n        return list[ch - \'a\'];\n    }\n\n    public void put(char ch, Node new_node) {\n        list[ch - \'a\'] = new_node;\n    }\n\n    public void inc(char ch) {\n        list[ch - \'a\'].count++;\n    }\n\n    public int retCount(char ch) {\n        return list[ch - \'a\'].count;\n    }\n}\n\nclass Solution {\n    private Node root;\n\n    public Solution() {\n        root = new Node();\n    }\n\n    public void insert(String word) {\n        Node node = root;\n        for (char ch : word.toCharArray()) {\n            if (!node.containKey(ch)) {\n                node.put(ch, new Node());\n            }\n            node.inc(ch);\n            node = node.get(ch);\n        }\n    }\n\n    public int search(String word) {\n        Node node = root;\n        int preCount = 0;\n        for (char ch : word.toCharArray()) {\n            preCount += node.retCount(ch);\n            node = node.get(ch);\n        }\n        return preCount;\n    }\n\n    public int[] sumPrefixScores(String[] words) {\n        // This problem can be solved using the trie data structure\n        for (String word : words) {\n            insert(word);\n        }\n        int n = words.length;\n        int[] res = new int[n];\n        for (int i = 0; i < n; i++) {\n            res[i] = search(words[i]);\n        }\n        return res;\n    }\n}\n\n```\n```python []\nclass Node:\n    def __init__(self):\n        self.count = 0\n        self.list = [None] * 26\n\n    def containKey(self, ch):\n        return self.list[ord(ch) - ord(\'a\')] is not None\n\n    def get(self, ch):\n        return self.list[ord(ch) - ord(\'a\')]\n\n    def put(self, ch, new_node):\n        self.list[ord(ch) - ord(\'a\')] = new_node\n\n    def inc(self, ch):\n        self.list[ord(ch) - ord(\'a\')].count += 1\n\n    def retCount(self, ch):\n        return self.list[ord(ch) - ord(\'a\')].count\n\n\nclass Solution:\n    def __init__(self):\n        self.root = Node()\n\n    def insert(self, word):\n        node = self.root\n        for ch in word:\n            if not node.containKey(ch):\n                node.put(ch, Node())\n            node.inc(ch)\n            node = node.get(ch)\n\n    def search(self, word):\n        node = self.root\n        preCount = 0\n        for ch in word:\n            preCount += node.retCount(ch)\n            node = node.get(ch)\n        return preCount\n\n    def sumPrefixScores(self, words):\n        # This problem can be solved using the trie data structure\n        for word in words:\n            self.insert(word)\n\n        res = []\n        for word in words:\n            preCount = self.search(word)\n            res.append(preCount)\n\n        return res\n\n```\n\n```cpp []\nstruct Node{\n    int count=0;\n    Node *list[26]={NULL};\n    bool containKey(char ch){\n        return list[ch-\'a\']!=NULL;\n    }\n    Node *get(char ch){\n        return list[ch-\'a\'];\n    }\n    void put(char ch,Node *new_node){\n        list[ch-\'a\']=new_node;\n    }\n    void inc(char ch){\n        list[ch-\'a\']->count+=1;\n    }\n    int retCount(char ch){\n        return list[ch-\'a\']->count;\n    }\n};\nclass Solution {\nprivate:\nNode *root;\npublic:\n    Solution(){\n        root=new Node;\n    }\n    void insert(string word){\n        Node *node=root;\n        for(auto ch:word){\n            if(!node->containKey(ch)){\n                node->put(ch,new Node);\n            }\n            node->inc(ch);\n            node=node->get(ch);\n        }\n    }\n    int search(string word){\n        Node *node=root;\n        int preCount=0;\n        for(auto ch:word){\n            preCount+=node->retCount(ch);\n            node=node->get(ch);\n        }\n        return preCount;\n    }\n    vector<int> sumPrefixScores(vector<string>& words) {\n        //This problem can be solved using the trie data structure\n        for(auto word:words){\n            insert(word);\n        }\n        int n=words.size();\n        vector<int>res(n);\n        for(int i=0;i<n;i++){\n            int preCount=search(words[i]);\n            res[i]=preCount;\n        }\n        return res;\n    }\n};\n```\n![olyQ7KgeQD6C37Sea5Uptw.webp](https://assets.leetcode.com/users/images/ea6ffb40-1318-442a-a1de-1431922e51c5_1727232201.291262.webp)\n
['Array', 'String', 'Trie', 'Counting', 'C++', 'Java', 'Python3']