Trie Solution || O(N*k) || Beats 97% || C++ || Python
Intuition\n Describe your first thoughts on how to solve this problem. \nUse a datastructure that allows quick prefix count\n\n# Approach\n Describe your approa
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUse a datastructure that allows quick prefix count\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Add each word to a trie\n- Increment score of nodes while adding words (except root node)\n- Run DFS for each word and add up those scores\n\n# Complexity\n- Time complexity: $$O(N*k)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(N*k)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nstruct Trie {\n    int score;\n    Trie *children[26];\n    Trie () {\n        score = 0;\n        memset(children, 0, sizeof(children));\n    }\n    void add(string &s, int i) {\n        if (i) score++;\n        if (i == s.size()) return;\n        if (!children[s[i]-\'a\']) children[s[i]-\'a\'] = new Trie();\n        children[s[i]-\'a\']->add(s, i+1);\n    }\n    int dfs(string &s, int i) {\n        if (i == s.size()) return score;\n        return score + children[s[i]-\'a\']->dfs(s, i+1);\n    }\n};\nclass Solution {\npublic:\n    vector<int> sumPrefixScores(vector<string>& words) {\n        Trie *trie = new Trie();\n        for (string &s : words) trie->add(s, 0);\n        vector<int> res;\n        for (string &s : words) res.push_back(trie->dfs(s, 0));\n        return res;\n    }\n};\n```\n```python []\nclass Trie:\n    def __init__(self):\n        self.score = 0\n        self.children = {}\n\n    def add(self, s: str, i: int):\n        if (i): self.score += 1\n        if (i == len(s)): return\n        if (not self.children.get(s[i])): self.children[s[i]] = Trie()\n        self.children[s[i]].add(s, i+1)\n\n    def dfs(self, s: str, i: int):\n        if (i == len(s)): return self.score\n        return self.score + self.children[s[i]].dfs(s, i+1)\n        \nclass Solution:\n    def sumPrefixScores(self, words: List[str]) -> List[int]:\n        trie = Trie()\n        for word in words:\n            trie.add(word, 0)\n        res = []\n        for word in words:\n            res.append(trie.dfs(word, 0))\n        return res\n        \n```
['String', 'Trie', 'C++', 'Python3']