Easy Solution | Explained with Example & Visual Walkthrough | Beginner Friendly |
Approach\nBuilding the Trie:\nEvery time a letter is inserted into the Trie, we update the count for that letter\u2019s node. This count keeps track of how many
# Approach\nBuilding the Trie:\nEvery time a letter is inserted into the Trie, we update the count for that letter\u2019s node. This count keeps track of how many words pass through that node.\n\nExample Words: ["abc", "ab", "bc", "b"]\n\nInsert "abc":\n\'a\' goes into the Trie (count is now 1).\n\'b\' goes into the Trie (count is now 1).\n\'c\' goes into the Trie (count is now 1).\n\n`root -> a(1) -> b(1) -> c(1)`\n\nInsert "ab":\n\'a\' already exists, so just increase the count (now 2).\n\'b\' already exists, so just increase the count (now 2).\n\n`root -> a(2) -> b(2) -> c(1)`\n\nInsert "bc":\n\'b\' doesn\'t exist directly to the root, so we create it (count is 1).\n\'c\' follows \'b\' (count is 1)\n\n```\nroot -> a(2) -> b(2) -> c(1)\n      \\\n       b(1) -> c(1)\n\n```\nInsert "b":\n\'b\' already exists under the root, so we just increase its count (now 2).\n```\nroot -> a(2) -> b(2) -> c(1)\n      \\\n       b(2) -> c(1)\n\n```\n\nCalculating Prefix Scores:\nFor each word, we traverse the Trie and sum up the counts of the nodes we visit.\n\nWord "abc":\nFrom the root and go through \'a\' (count = 2), \'b\' (count = 2), and \'c\' (count = 1).\nPrefix score = 2 + 2 + 1 = 5.\n\nWord "ab":\nFrom the root and go through \'a\' (count = 2) and \'b\' (count = 2).\nPrefix score = 2 + 2 = 4.\n\nWord "bc":\nFrom the root and go through \'b\' (count = 2) and \'c\' (count = 1).\nPrefix score = 2 + 1 = 3.\n\nWord "b":\nFrom the root and go through \'b\' (count = 2).\nPrefix score = 2 = 2.\n\n\nThe array of prefix scores will be: [5, 4, 3, 2]\n\n\nFinal Trie will be:\n```\n       (root)\n      /     \\\n    a(2)    b(2)\n    |       |\n    b(2)    c(1)\n    |\n    c(1)\n\n```\n\n#### Upvote if this solution is good \u2B06\uFE0F\n\n\n\n# Code\n```java []\nclass Solution {\n    class Trie{\n        Trie children[] =new Trie [26];\n        int count = 0;\n    }\n    public int[] sumPrefixScores(String[] words) {\n        Trie root = new Trie();\n        for(String s : words){\n            Trie curr = root;\n            for(char ch:s.toCharArray()){\n                if(curr.children[ch-\'a\']==null){\n                    curr.children[ch-\'a\']=new Trie();\n                }\n                curr = curr.children[ch-\'a\'];\n                curr.count++;\n            }\n        } \n        int n = words.length;\n        int ans[] = new int[n];\n        int i =0;\n        for(String s:words){\n            Trie curr = root;\n            int sum = 0;\n            for(char ch:s.toCharArray()){\n                curr = curr.children[ch-\'a\'];\n                sum+=curr.count;\n            }\n            ans[i]=sum;\n            i++;\n        }\n        return ans;\n    }\n}\n```
['Array', 'String', 'Trie', 'Counting', 'Java']