Java: Trie solution with comments and explanation. Easy to understand.
Intuition\nWe are given a array of words. For each word, we need to compute prefix score. Any word of length n has n prefixes. For example, word abcd has prefix
# Intuition\nWe are given a array of words. For each word, we need to compute $$prefix score.$$ Any word of length `n` has `n` prefixes. For example, word `abcd` has prefixes `a`, `ab`, `abc` and `abcd`. For each prefix we need to find number of times it occurs in the words array.\n\n# Approach\nFor each word, we add the word to the trie. Each node in the trie has a count field which indicates how many times the prefix has occurred. \n\nConsider the following array `[abcd, ab, acf, bad, bat, dog, dad]`\n![WhatsApp Image 2024-09-25 at 09.30.03_96e38eb6.jpg](https://assets.leetcode.com/users/images/11a38b81-7562-48d5-bcc0-042548a805dd_1727236896.2791138.jpeg)\n\nIn the above diagarm, you could see the count for each prefix in the trie node.\n\n# Complexity\n- Time complexity: $\\sum_{i = 1}^{n} (NumChars(Word_i))$\n\n- Space complexity: $\\sum_{i = 1}^{n} (NumChars(Word_i))$\n\n# Code\n```java []\nclass Solution {\n    public int[] sumPrefixScores(String[] words) {\n        TrieNode trie = new TrieNode();\n        for (String word : words)\n            insert(word, trie);\n        \n        int[] resArr = new int[words.length];\n        int resIdx = 0;\n        for (String word : words)\n            resArr[resIdx++] = findCount(word, trie);\n        \n        return resArr;\n    }\n\n    /**\n        Function to find overall prefix count of word.\n        We traverse each character in the trie and collect the counts for each prefix as we traverse the tree.\n    **/\n    private int findCount(String word, TrieNode trie) {\n        TrieNode curNode = trie;\n        int res = 0;\n        for (int i = 0; i < word.length(); i++) {\n            int nodeId = word.charAt(i) - \'a\';\n            curNode = curNode.charNodes[nodeId];\n            if (curNode == null)\n                break;  // This should be unreachable since we should have all nodes once we insert the word.\n            res += curNode.count;\n        }\n\n        return res;\n    }\n\n    // Function to insert word into Trie.\n    private void insert(String word, TrieNode trie) {\n        TrieNode curNode = trie;\n\n        for (int i = 0; i < word.length(); i++) {\n            int nodeId = word.charAt(i) - \'a\';\n            if (curNode.charNodes[nodeId] == null)\n                curNode.charNodes[nodeId] = new TrieNode();\n            curNode = curNode.charNodes[nodeId];\n            curNode.count++;\n        }\n    }\n\n    class TrieNode {\n        public TrieNode[] charNodes;\n        public int count;\n\n        public TrieNode() {\n            charNodes = new TrieNode[26];\n            count = 0;\n        }\n    }\n}\n```
['Trie', 'Java']