2 Approaches || Trie & Hashing
Intuition\n Describe your first thoughts on how to solve this problem. \nTrie:\nTrie approach leverages the tree structure to store and count the frequency of e
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n**Trie:**\nTrie approach leverages the tree structure to store and count the frequency of each prefix. Each node in the Trie represents a prefix formed by the characters from the root to that node. As words are inserted into the Trie, we track how many times each prefix has been encountered. This allows us to quickly compute the sum of prefix scores for any word by traversing its corresponding path in the Trie and summing the counts stored in the nodes. The Trie structure is ideal for efficiently handling problems related to prefixes in multiple strings.\n\n**Hashing:**\nHashing approach calculates a unique hash value for each prefix of a word and uses an unordered map to store the frequency of each prefix across all words. As we iterate through each string, we update the hash and check the map to count how many times each prefix has appeared. After processing the strings, we calculate the prefix score for each word by summing the frequencies of its prefixes stored in the map. This method is faster for lookups and requires less memory in comparison to a Trie but lacks the structural benefits of the Trie.\n\n---\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**Trie Approach:**\n- Initialize a Trie where each node represents a character from \'a\' to \'z\'.\n- For each word, traverse its characters and insert them into the Trie.\n- As you insert a character, update the x value (prefix count) in the corresponding Trie node.\n- Ensure that new nodes are created for characters not already present in the current path.\n- Repeat the process for all words to fully construct the Trie with prefix counts.\n- To compute the prefix score for a word, traverse its characters in the Trie.\n- Sum the x values (prefix counts) encountered along the path of the word.\n- Store the prefix sum for each word in a result array.\n\n\n**Hashing Approach:**\n- Initialize an unordered map to track the frequency of each prefix\u2019s hash.\n- For each word, iterate through its characters, calculating a rolling hash for each prefix.\n- For each calculated hash, increment its count in the map to track the prefix\u2019s occurrences.\n- Repeat the process for all words, updating the prefix counts in the map.\n- To compute the prefix score for a word, iterate through its characters and recalculate the prefix hashes.\n- For each prefix hash of a word, sum the frequency stored in the map.\n- Repeat this for all words, summing the counts of their respective prefixes.\n- Store the prefix sum for each word in a result array.\n\n\n---\n\n\n\n## For better understanding and detailed explanation see inline comments \n\n---\n\n\n\n# Complexity\n- Time complexity: O(N.M)-> Both Approaches\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N.M)-> Both Approaches\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n---\n\n![Screenshot 2024-09-10 at 4.31.30\u202FPM.png](https://assets.leetcode.com/users/images/5643ad38-eb76-422a-956f-bd67ed21d48e_1727235137.2978961.png){:style=\'width:250px\'}\n\n# Code\n**Trie:**\n```cpp []\n// Trie Node definition\nclass trie {\n    public:\n        int x;  // To store how many times the prefix ending at this node has been seen.\n        trie *v[26];  // Array of pointers to children nodes for each character \'a\' to \'z\'.\n};\n\n// Function to insert a string into the Trie and update prefix counts\nvoid maketrie(string str, trie* node) {\n    for (auto &i: str) {  // Traverse each character in the string\n        // If the node for this character doesn\'t exist, create it\n        if (node->v[i - \'a\'] == NULL) {\n            node->v[i - \'a\'] = new trie();  // Create a new Trie node\n            node = node->v[i - \'a\'];  // Move to the newly created node\n            node->x = node->x + 1;  // Increment the count for this prefix\n        } else {\n            node = node->v[i - \'a\'];  // Move to the existing node\n            node->x = node->x + 1;  // Increment the count for this prefix\n        }\n    }\n}\n\n// Function to calculate the sum of prefix scores for a given string\nvoid solve(string str, trie* node, int &x) {\n    trie* p = node;  // Pointer to traverse the Trie\n    for (auto &i: str) {  // Traverse each character in the string\n        p = p->v[i - \'a\'];  // Move to the next node in the Trie\n        x += p->x;  // Add the count of this prefix to the total score\n    }\n}\n\n// Main solution class\nclass Solution {\npublic:\n    // Function to calculate sum of prefix scores for all words\n    vector<int> sumPrefixScores(vector<string>& words) {\n        trie *node = new trie();  // Create the root node of the Trie\n        \n        // Step 1: Insert each word into the Trie and build the prefix tree\n        for (auto &i: words) {\n            maketrie(i, node);  // Insert word into the Trie\n        }\n        \n        vector<int> ans;  // Vector to store the final prefix scores\n        int x = 0;  // Variable to store the current score for a word\n        \n        // Step 2: Calculate the prefix score for each word\n        for (auto &i: words) {\n            x = 0;  // Reset the score for the new word\n            solve(i, node, x);  // Calculate the prefix score for the current word\n            ans.push_back(x);  // Store the score in the answer vector\n        }\n        \n        return ans;  // Return the final list of prefix scores\n    }\n};\n\n```\n**Hashing:**\n```cpp []\nclass Solution {\npublic:\n    vector<int> sumPrefixScores(vector<string>& nums) {\n        int n = nums.size();  // Get the number of strings in the input.\n        unordered_map<long long, int> mp;  // Hash map to store the count of each unique prefix hash.\n        long long mod = 1e15 + 7;  // A large prime number used as a modulus to avoid overflow in hash computation.\n        \n        // Step 1: Calculate and store the hash of each prefix for all strings.\n        for (int i = 0; i < n; i++) {\n            long long hash = 0;  // Initialize hash for the current string.\n            for (auto &ch : nums[i]) {  // For each character in the current string:\n                hash = (hash * 97 + (ch)) % mod;  // Update the hash using the current character.\n                mp[hash]++;  // Increment the count of this particular prefix hash in the map.\n            }\n        }\n\n        // Step 2: Calculate the prefix score for each string.\n        vector<int> ans(n, 0);  // Initialize the result vector to store prefix scores for each string.\n        for (int i = 0; i < n; i++) {\n            int count = 0;  // To store the sum of prefix scores for the current string.\n            long long hash = 0;  // Initialize hash for the current string.\n            for (auto &ch : nums[i]) {  // For each character in the current string:\n                hash = (hash * 97 + (ch)) % mod;  // Recalculate the hash for each prefix.\n                count += mp[hash];  // Add the count of this prefix from the hash map to the score.\n            }\n            ans[i] = count;  // Store the total prefix score for this string.\n        }\n\n        return ans;  // Return the vector of prefix scores.\n    }\n};\n```
['Array', 'Hash Table', 'String', 'Trie', 'Counting', 'C++']