All solutions
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\n\nclass Solution {\n    public int[] sumPrefixScores(String[] words) {\n        int n = words.length;\n        int[] answer = new int[n];\n        \n        for (int i = 0; i < n; i++) {\n            String word = words[i];\n            for (int j = 1; j <= word.length(); j++) {\n                String prefix = word.substring(0, j);\n                for (String w : words) {\n                    if (w.startsWith(prefix)) {\n                        answer[i]++;\n                    }\n                }\n            }\n        }\n        \n        return answer;\n    }\n}\n```\n```java []\nclass Solution {\n    public int[] sumPrefixScores(String[] words) {\n        TreeMap<String, Integer> prefixCount = new TreeMap<>();\n        \n        // Count all prefixes\n        for (String word : words) {\n            for (int i = 1; i <= word.length(); i++) {\n                String prefix = word.substring(0, i);\n                prefixCount.put(prefix, prefixCount.getOrDefault(prefix, 0) + 1);\n            }\n        }\n        \n        // Calculate scores\n        int[] answer = new int[words.length];\n        for (int i = 0; i < words.length; i++) {\n            String word = words[i];\n            int score = 0;\n            for (int j = 1; j <= word.length(); j++) {\n                String prefix = word.substring(0, j);\n                score += prefixCount.get(prefix);\n            }\n            answer[i] = score;\n        }\n        \n        return answer;\n    }\n}\n```\n```java []\nclass Solution {\n    class TrieNode {\n        TrieNode[] children;\n        int count;\n\n        TrieNode() {\n            children = new TrieNode[26];\n            count = 0;\n        }\n    }\n\n    public int[] sumPrefixScores(String[] words) {\n        TrieNode root = new TrieNode();\n        int n = words.length;\n\n        // Build the Trie\n        for (String word : words) {\n            TrieNode node = root;\n            for (char c : word.toCharArray()) {\n                int index = c - \'a\';\n                if (node.children[index] == null) {\n                    node.children[index] = new TrieNode();\n                }\n                node = node.children[index];\n                node.count++;\n            }\n        }\n\n        // Calculate prefix scores\n        int[] answer = new int[n];\n        for (int i = 0; i < n; i++) {\n            TrieNode node = root;\n            for (char c : words[i].toCharArray()) {\n                node = node.children[c - \'a\'];\n                answer[i] += node.count;\n            }\n        }\n\n        return answer;\n    }\n}\n```\n\n| Solution   | Time Complexity           | Space Complexity |\n|------------|---------------------------|-------------------|\n| Brute Force| O(n * m^2)                | O(1)              |\n| Trie       | O(N * L)                  | O(N)              |\n| TreeMap    | O(N * L * log(N * L))     | O(N * L)          |\n\nWhere:\n- n = number of words\n- m = length of the longest word\n- N = total number of characters across all words\n- L = average length of words\n\nDetailed Explanation:\n\n1. Brute Force Solution:\n   - Time: O(n * m^2)\n     - We iterate through each word (n)\n     - For each word, we generate all prefixes (up to m)\n     - For each prefix, we check against all words (n)\n   - Space: O(1)\n     - We only use a fixed-size array to store the results\n\n2. Trie-based Solution:\n   - Time: O(N * L)\n     - We iterate through all characters of all words once to build the Trie\n     - We iterate through all characters again to calculate scores\n   - Space: O(N)\n     - In the worst case (no common prefixes), we store all characters in the Trie\n\n3. TreeMap-based Solution:\n   - Time: O(N * L * log(N * L))\n     - We generate all prefixes (N * L operations)\n     - Each TreeMap operation (put/get) takes log(N * L) time\n   - Space: O(N * L)\n     - We store all prefixes as strings in the TreeMap\n\n\n### Hashmap solution\n\n```java []\n\n/*  TLE same as TreeMap.\n\nTime Complexity: O(N * L^2)\n\nN is the number of words\nL is the average length of the words\n\n\nCounting prefixes:\n\nWe iterate through each word: O(N)\nFor each word, we generate all prefixes: O(L)\nSubstring operation and HashMap put: O(L)\nTotal: O(N * L^2)\n\n\nCalculating scores:\n\nWe iterate through each word again: O(N)\nFor each word, we generate all prefixes: O(L)\nHashMap get and sum: O(1)\nTotal: O(N * L^2)\n*/\n\nclass Solution {\n    public int[] sumPrefixScores(String[] words) {\n        List<Integer> res = new ArrayList<>();\n        Map<String, Integer> count = new HashMap<>();\n        \n        // Count prefixes\n        for (String w : words) {\n            for (int i = 1; i <= w.length(); i++) {\n                String prefix = w.substring(0, i);\n                count.put(prefix, count.getOrDefault(prefix, 0) + 1);\n            }\n        }\n        \n        // Calculate scores\n        for (String w : words) {\n            int score = 0;\n            for (int i = 1; i <= w.length(); i++) {\n                score += count.get(w.substring(0, i));\n            }\n            res.add(score);\n        }\n        \n        // Convert List<Integer> to int[] without streams\n        int[] resultArray = new int[res.size()];\n        for (int i = 0; i < res.size(); i++) {\n            resultArray[i] = res.get(i);\n        }\n        \n        return resultArray;\n    }\n}\n\n\n```
['Java']