JAVA EASY SOLUTION
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires counting how many strings in the given list start with each prefix
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires counting how many strings in the given list start with each prefix of every word. A naive approach would be to check each prefix of every word against all other words, but this would be inefficient. Using a Trie `(Prefix Tree)` can help us efficiently track and count how many words share each prefix as we process the input list.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Trie Construction: We construct a Trie where each node represents a character and holds the count of how many words pass through that node. This allows us to keep track of how many words have a certain prefix.\n\n2. Insertion: We insert each word into the Trie, updating the count at each node (representing a prefix).\n\n3. Prefix Score Calculation: For each word, we traverse through the Trie and accumulate the scores of its prefixes by summing the counts stored at each node corresponding to the word\'s prefixes.\n\n4. Efficiency: By using a Trie, we ensure that the prefix counts are shared across different words, making the solution more efficient than comparing each prefix to every word individually.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity is \n\uD835\uDC42(\uD835\uDC5B*\uD835\uDC3F)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\uD835\uDC42(\uD835\uDC5B*\uD835\uDC3F)\n# Code\n```java []\nclass TrieNode {\n    Map<Character, TrieNode> children;\n    int count;\n\n    public TrieNode() {\n        children = new HashMap<>();\n        count = 0;\n    }\n}\nclass Trie {\n    private TrieNode root;\n\n    public Trie() {\n        root = new TrieNode();\n    }\n    public void insert(String word) {\n        TrieNode node = root;\n        for (char c : word.toCharArray()) {\n            if (!node.children.containsKey(c)) {\n                node.children.put(c, new TrieNode());\n            }\n            node = node.children.get(c);\n            node.count++;\n        }\n    }\n    public int getScore(String word) {\n        TrieNode node = root;\n        int score = 0;\n        for (char c : word.toCharArray()) {\n            node = node.children.get(c);\n            score += node.count;\n        }\n        return score;\n    }\n}\nclass Solution {\n    public int[] sumPrefixScores(String[] words) {\n        Trie trie = new Trie();\n        \n        for (String word : words) {\n            trie.insert(word);\n        }\n\n       \n        int[] result = new int[words.length];\n        for (int i = 0; i < words.length; i++) {\n            result[i] = trie.getScore(words[i]);\n        }\n\n        return result;\n    }\n}\n```
['Trie', 'Prefix Sum', 'Java']