Full Dry Run + Brute to Trie Explained, illustrations || Let's Go !!
Youtube Explanation\nSoon to be on Channel : https://www.youtube.com/@Intuit_and_Code\nEdited:\nhttps://youtu.be/Sh0ca33JjMM?si=9tzS3AuxGtHSgkew\n\n# Intuition 
# Youtube Explanation\nSoon to be on Channel : https://www.youtube.com/@Intuit_and_Code\nEdited:\nhttps://youtu.be/Sh0ca33JjMM?si=9tzS3AuxGtHSgkew\n\n# Intuition & Approach\n\n> If you don\'t know trie, don\'t worry this article will help you get an idea about how it works.\n\n![image.png](https://assets.leetcode.com/users/images/40f2fa50-2a87-4087-b7fc-9a5358b45274_1727229888.6907105.png)\n![image.png](https://assets.leetcode.com/users/images/97f6f078-58d7-43be-ab83-d67ff9fc969b_1727229899.4832387.png)\n![image.png](https://assets.leetcode.com/users/images/a99d79a1-29b2-44af-a4cf-4856b230cfb0_1727230028.1686428.png)\n![image.png](https://assets.leetcode.com/users/images/99054a26-499f-4612-ab6a-307a377881b6_1727230056.016513.png)\n![image.png](https://assets.leetcode.com/users/images/ae814eee-fc04-45c9-8bbb-554a7eac44a3_1727230084.0293288.png)\n![image.png](https://assets.leetcode.com/users/images/15408778-b74f-420b-8f4b-726f95581436_1727230103.3956208.png)\n![image.png](https://assets.leetcode.com/users/images/dc3dcae5-4a43-4c3b-b4ba-25df56b4b173_1727230128.0340014.png)\n![image.png](https://assets.leetcode.com/users/images/9468318c-661c-40ae-9188-f389cd566a14_1727230141.0762591.png)\n\n> We can also use vector of size 26 to make more faster in rate of submission time\n\n![image.png](https://assets.leetcode.com/users/images/861a5d56-2b3c-493c-92b7-392bf1da0b46_1727230158.881807.png)\n![image.png](https://assets.leetcode.com/users/images/ce1b0622-61b7-4b0f-9b9b-480d3e84bb0c_1727230168.3331869.png)\n![image.png](https://assets.leetcode.com/users/images/b4f6202c-e280-46a7-87c8-91e31eb9bed6_1727230182.9469376.png)\n![image.png](https://assets.leetcode.com/users/images/aaa65b5d-280a-401e-ab2b-719368148371_1727230197.4238646.png)\n\n\n# Complexity\n- Time complexity: O( n * k)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O( n * k)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nstruct Node{\n    unordered_map<char,pair<int,Node*>> umc;\n    bool is_end=false;\n};\n\nclass Trie{\nprivate:\n    Node *root;\npublic:\n    // constructor always gets called when class is called\n    // help us to always keep track of first head node\n    Trie(){\n        root = new Node();\n    }\n\n    // insertion function\n    void insert(string s){\n        Node *cur = root;\n        for(int i=0;i<s.size();i++){\n            if(cur->umc.find(s[i]) == cur->umc.end()){\n                cur->umc[s[i]].second = new Node();\n            }\n\n            cur->umc[s[i]].first++;\n            cur = cur->umc[s[i]].second;\n        }\n\n        cur->is_end = true;\n        return;\n    }\n\n    // function to match the prefix\n    int check_prefix_count(string s){\n        Node *cur = root;\n        int count = 0;\n\n        for(int i=0;i<s.size();i++){\n            if(cur->umc.find(s[i]) == cur->umc.end()){\n                break;\n            }\n\n            count += cur->umc[s[i]].first;\n            cur = cur->umc[s[i]].second;\n        }\n         \n        return count;\n    }\n};\n\nclass Solution {\npublic:\n    vector<int> sumPrefixScores(vector<string>& words) {\n        Trie t; // initiate trie\n\n        for(auto &word:words){ // for(int i=0;i<words.size();i++)\n            t.insert(word); // word = words[i]\n        }\n\n        vector<int> ans;\n        for(auto &word:words){ \n            int tmp = t.check_prefix_count(word); \n            ans.push_back(tmp);\n        }\n\n        return ans;\n    }\n};\n```\n``` C++ [ ]\nstruct Node {\n    int count = 0;\n    Node* list[26] = {nullptr};  // Array for 26 lowercase English letters\n};\n\nclass Solution {\nprivate:\n    Node* root;\npublic:\n    Solution() {\n        root = new Node();\n    }\n\n    // Insertion function to add words to the Trie\n    void insert(const string& word) {\n        Node* node = root;\n        for (char ch : word) {\n            // If the current character\'s node doesn\'t exist, create a new one\n            if (node->list[ch - \'a\'] == nullptr) {\n                node->list[ch - \'a\'] = new Node();\n            }\n            // Increment the count of the current node for this character\n            node->list[ch - \'a\']->count++;\n            // Move to the next node (child)\n            node = node->list[ch - \'a\'];\n        }\n    }\n\n    // Search function to calculate prefix score\n    int search(const string& word) {\n        Node* node = root;\n        int preCount = 0;\n        for (char ch : word) {\n            // Add the count of the current character\'s node to prefix score\n            preCount += node->list[ch - \'a\']->count;\n            // Move to the next node (child)\n            node = node->list[ch - \'a\'];\n        }\n        return preCount;\n    }\n\n    // Function to compute the sum of prefix scores for all words\n    vector<int> sumPrefixScores(vector<string>& words) {\n        // Insert all words into the Trie\n        for (auto& word : words) {\n            insert(word);\n        }\n\n        int n = words.size();\n        vector<int> res(n);\n\n        // Calculate prefix score for each word\n        for (int i = 0; i < n; i++) {\n            int preCount = search(words[i]);\n            res[i] = preCount;\n        }\n\n        return res;\n    }\n};\n```\n``` java [ ]\nclass Node {\n    Map<Character, Pair> umc = new HashMap<>();\n    boolean isEnd = false;\n}\n\nclass Pair {\n    int count;\n    Node node;\n\n    Pair(int count, Node node) {\n        this.count = count;\n        this.node = node;\n    }\n}\n\nclass Trie {\n    private Node root;\n\n    public Trie() {\n        root = new Node();\n    }\n\n    // Insert word into the Trie\n    public void insert(String s) {\n        Node cur = root;\n        for (int i = 0; i < s.length(); i++) {\n            char c = s.charAt(i);\n            if (!cur.umc.containsKey(c)) {\n                cur.umc.put(c, new Pair(0, new Node()));\n            }\n            cur.umc.get(c).count++;\n            cur = cur.umc.get(c).node;\n        }\n        cur.isEnd = true;\n    }\n\n    // Check prefix count of the word\n    public int checkPrefixCount(String s) {\n        Node cur = root;\n        int count = 0;\n        for (int i = 0; i < s.length(); i++) {\n            char c = s.charAt(i);\n            if (!cur.umc.containsKey(c)) {\n                break;\n            }\n            count += cur.umc.get(c).count;\n            cur = cur.umc.get(c).node;\n        }\n        return count;\n    }\n}\n\nclass Solution {\n    public int[] sumPrefixScores(String[] words) {\n        Trie trie = new Trie();\n        \n        // Insert all words into the Trie\n        for (String word : words) {\n            trie.insert(word);\n        }\n\n        // Collect the prefix scores for each word\n        int[] ans = new int[words.length];\n        for (int i = 0; i < words.length; i++) {\n            ans[i] = trie.checkPrefixCount(words[i]);\n        }\n\n        return ans;\n    }\n}\n```
['Array', 'String', 'Trie', 'String Matching', 'Counting', 'C++', 'Java']