[Java/Python 3] Trie build/search prefix w/ brief explanation and analysis.
Build Trie and accumulate the frequencies of each pefix at the same time; then search each word and compute the corresponding score.\n\njava\nclass Trie {\n    
Build Trie and accumulate the frequencies of each pefix at the same time; then search each word and compute the corresponding score.\n\n```java\nclass Trie {\n    int cnt = 0;\n    Map<Character, Trie> kids = new HashMap<>();\n    public void add(String word) {\n        Trie t = this;\n        for (char c : word.toCharArray()) {\n            if (!t.kids.containsKey(c)) {\n                t.kids.put(c, new Trie());\n            }\n            t = t.kids.get(c);\n            t.cnt += 1;\n        }\n    }\n    public int search(String word) {\n        Trie t = this;\n        int score = 0;\n        for (char c : word.toCharArray()) {\n            if (t.kids.get(c) == null) {\n                 return score;\n            }\n            t = t.kids.get(c);\n            score += t.cnt;\n        }\n        return score;\n    }\n}\n\nclass Solution {\n    public int[] sumPrefixScores(String[] words) {\n        Trie root = new Trie();\n        for (String word : words) {\n            root.add(word);\n        }\n        int n = words.length, i = 0;\n        int[] scores = new int[n];\n        for (String word : words) {\n            scores[i++] = root.search(word);\n        }\n        return scores;\n    }\n}\n```\n```python\nclass Trie:\n    def __init__(self):\n        self.cnt = 0\n        self.kids = {}\n    def add(self, word: str) -> None:\n        trie = self\n        for c in word:\n            if c not in trie.kids:\n                trie.kids[c] = Trie()\n            trie = trie.kids[c]\n            trie.cnt += 1\n    def search(self, word) -> int:\n        score = 0\n        trie = self\n        for c in word:\n            if c not in trie.kids:\n                return score\n            trie = trie.kids[c]        \n            score += trie.cnt\n        return score\n    \nclass Solution:\n    def sumPrefixScores(self, words: List[str]) -> List[int]:\n        root = Trie()\n        for w in words:\n            root.add(w)\n        return [root.search(w) for w in words]\n```\n\n**Analysis:**\n\nTime & space: `O(n * w)`, where `n = words.length, w =` average size of word in `words`.
[]