💡 O(n⋅m) | Easy Solution | C++ 462ms Beats 87.78%  | Java Py3
\n#\n---\n\n# Intuition\nWe can efficiently solve this problem using a Trie (prefix tree). A Trie helps in storing prefixes and counting their occurrences while
\n#\n---\n\n# **Intuition**\nWe can efficiently solve this problem using a **Trie** (prefix tree). A **Trie** helps in storing prefixes and counting their occurrences while reducing redundant comparisons. Each node in the Trie represents a character, and we increment the count for each character as we insert the strings. Once the Trie is built, we can quickly compute the prefix scores by traversing the Trie for each word.\n\n\n# **Approach**\nTo solve the problem, we first construct a Trie by inserting each string character by character, incrementing the count for each node to track how many strings share that prefix. After building the Trie, we compute the prefix scores for each string by traversing the Trie and summing the counts of the nodes corresponding to each prefix, allowing us to efficiently determine the total score for every non-empty prefix of each string.\n\n# **Complexity**\n- **Time Complexity** $$O(n \\cdot m)$$, where $$n$$ is the number of words, and $$m$$ is the average length of the words. We traverse each word multiple times: once for building the Trie and once for calculating the prefix scores.\n\n- **Space Complexity** $$O(n \\cdot m)$$ for storing the Trie.\n\n---\n\n# **Code**\n```cpp []\nstruct T {\n    T* c[26] = {};\n    int cnt = 0;\n};\nclass Solution {\npublic:\n    vector<int> sumPrefixScores(vector<string>& w) {\n        T* r = new T();  \n        for (auto& s : w) \n            for (T* n = r; auto ch : s) \n                n = n->c[ch - \'a\'] ? n->c[ch - \'a\'] : n->c[ch - \'a\'] = new T(), n->cnt++;\n        vector<int> res;\n        for (auto& s : w) {\n            int sc = 0;\n            for (T* n = r; auto ch : s) \n                sc += (n = n->c[ch - \'a\'])->cnt;\n            res.push_back(sc);\n        }\n        return res;\n    }\n};\nauto io_opt = [] { ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();\n```\n```java []\nclass Solution {\n    class TrieNode {\n        TrieNode[] children = new TrieNode[26];\n        int count = 0;\n    } \n    public int[] sumPrefixScores(String[] words) {\n        TrieNode root = new TrieNode();\n        for (String word : words) {\n            TrieNode node = root;\n            for (char ch : word.toCharArray()) {\n                if (node.children[ch - \'a\'] == null) {\n                    node.children[ch - \'a\'] = new TrieNode();\n                }\n                node = node.children[ch - \'a\'];\n                node.count++;\n            }\n        }\n        int[] result = new int[words.length];\n        for (int i = 0; i < words.length; i++) {\n            TrieNode node = root;\n            int score = 0;\n            for (char ch : words[i].toCharArray()) {\n                node = node.children[ch - \'a\'];\n                score += node.count;\n            }\n            result[i] = score;\n        }\n        return result;\n    }\n}\n```\n```python3 []\nclass TrieNode:\n    def __init__(self):\n        self.children = {}\n        self.count = 0\nclass Solution:\n    def sumPrefixScores(self, words: List[str]) -> List[int]:\n        root = TrieNode()\n        for word in words:\n            node = 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        result = []\n        for word in words:\n            node = root\n            score = 0\n            for ch in word:\n                node = node.children[ch]\n                score += node.count\n            result.append(score)\n        return result\n```\n---\n- ![image.png](https://assets.leetcode.com/users/images/33599343-e7e4-47b0-8436-23a4d4888621_1727233098.2279394.png)\n- ![Designer.png](https://assets.leetcode.com/users/images/5395952a-4267-4b87-b81f-f28780669704_1726803172.327018.png)\n\n\n\n---\n\n
['Trie', 'C++', 'Java', 'Python3']