🌟 Multi-Language Solution for Prefix Score Mastery Made Easy 🔥💯
\n\nExplore a collection of solutions to LeetCode problems in multiple programming languages. Each solution includes a detailed explanation and step-by-step app
![Screenshot 2024-07-02 113653.png](https://assets.leetcode.com/users/images/22b27ce5-85a0-45cc-89aa-31733bd82399_1727228994.2532544.png)\n\nExplore a collection of solutions to LeetCode problems in multiple programming languages. Each solution includes a detailed explanation and step-by-step approach to solving the problem efficiently. Whether you\'re a beginner looking to learn or an experienced coder seeking optimized solutions, this repository aims to provide clear and insightful approaches to tackling challenging LeetCode problems.\n\n### **Access daily LeetCode Solutions Repo :** [click here](https://github.com/withaarzoo/LeetCode-Solutions)\n\n---\n\n![image.png](https://assets.leetcode.com/users/images/0047bc6d-37c3-48d6-b632-3f8318a12a87_1727228977.7951622.png)\n\n---\n\n# Intuition\n<!-- Describe your initial thoughts and strategy to solve this problem. -->\nThe problem asks us to find the sum of scores for each string\'s prefixes in the list. A brute-force approach would require generating all prefixes and counting their occurrences, but this would be inefficient. Instead, we can optimize this by using a **Trie (Prefix Tree)**. By inserting each word into the Trie, we can track how many words share a common prefix and efficiently compute the required prefix sums.\n\n---\n\n# Approach\n<!-- Detail the specific method and steps you used to solve the problem. -->\n1. **Trie Construction**: We will insert each word into a Trie, where each node represents a character. As we insert each character, we will count how many times it has been visited.\n2. **Prefix Calculation**: Once the Trie is constructed, for each word, we traverse its characters and sum the counts stored at the corresponding nodes, which represent how many words share that prefix.\n3. **Result Storage**: For each word, we store the cumulative sum of scores for its prefixes in the result array.\n\n---\n\n# Complexity\n- **Time complexity**:  \n  $$O(n \\cdot m)$$, where \\(n\\) is the number of words and \\(m\\) is the average length of the words.  \n  We insert each character of each word into the Trie, and then traverse the Trie again to calculate prefix scores.\n\n- **Space complexity**:  \n  $$O(n \\cdot m)$$, where \\(n\\) is the number of words and \\(m\\) is the average length of the words.  \n  The Trie stores all characters of the words and their corresponding prefix counts.\n\n---\n\n# Code\n```C++ []\n#include <iostream>\n#include <vector>\n#include <unordered_map>\n\nusing namespace std;\n\n// Structure to define a TrieNode\n// Each node will store its children (mapped by characters) and the count of words passing through it\nstruct TrieNode {\n    // A map to store the children nodes corresponding to each character\n    unordered_map<char, TrieNode*> children;\n    \n    // This variable keeps track of how many words share this node (i.e., pass through this prefix)\n    int count = 0;\n};\n\n// Class that implements the Trie (prefix tree) data structure\nclass Trie {\npublic:\n    // Root node of the Trie\n    TrieNode* root;\n\n    // Constructor to initialize the root node of the Trie\n    Trie() {\n        root = new TrieNode();\n    }\n\n    // Function to insert a word into the Trie\n    // For each character in the word, it will either create a new node or traverse an existing one\n    void insert(const string& word) {\n        TrieNode* node = root;  // Start from the root node\n        for (char ch : word) {   // Iterate through each character in the word\n            // If the character is not already a child of the current node, create a new TrieNode\n            if (!node->children.count(ch)) {\n                node->children[ch] = new TrieNode();\n            }\n            // Move to the child node corresponding to the character\n            node = node->children[ch];\n            // Increment the count to indicate that one more word passes through this prefix\n            node->count++;\n        }\n    }\n\n    // Function to calculate the sum of scores for all prefixes of the given word\n    // The score for a prefix is the number of words that have this prefix\n    int getPrefixScoreSum(const string& word) {\n        TrieNode* node = root;  // Start from the root node\n        int scoreSum = 0;       // Initialize the total score sum to 0\n        for (char ch : word) {  // Iterate through each character in the word\n            // Move to the child node corresponding to the character\n            node = node->children[ch];\n            // Add the count of words passing through this prefix (the current node) to the score sum\n            scoreSum += node->count;\n        }\n        // Return the total score sum for all prefixes of the word\n        return scoreSum;\n    }\n};\n\n// Solution class to calculate the sum of prefix scores for a list of words\nclass Solution {\npublic:\n    // Function that calculates the sum of prefix scores for each word in the input vector\n    vector<int> sumPrefixScores(vector<string>& words) {\n        Trie trie;  // Create an instance of the Trie\n\n        // Insert all words into the Trie\n        for (const string& word : words) {\n            trie.insert(word);  // Insert each word into the Trie\n        }\n\n        // Calculate the sum of prefix scores for each word\n        vector<int> result;  // Vector to store the prefix score sums for all words\n        for (const string& word : words) {\n            // For each word, calculate the sum of scores for its prefixes using the Trie\n            result.push_back(trie.getPrefixScoreSum(word));\n        }\n\n        // Return the result containing prefix score sums for all words\n        return result;\n    }\n};\n\n```\n```Java []\nimport java.util.HashMap;\n\n// Class representing a single node in the Trie\nclass TrieNode {\n    // HashMap to store child nodes for each character\n    HashMap<Character, TrieNode> children = new HashMap<>();\n    \n    // Count stores how many times this node has been visited (useful for scoring prefixes)\n    int count = 0;\n}\n\n// Class representing the Trie (prefix tree) structure\nclass Trie {\n    TrieNode root; // Root node of the Trie\n\n    // Constructor to initialize the Trie with an empty root node\n    public Trie() {\n        root = new TrieNode();\n    }\n\n    // Method to insert a word into the Trie\n    public void insert(String word) {\n        TrieNode node = root; // Start at the root node\n        \n        // Loop through each character in the word\n        for (char ch : word.toCharArray()) {\n            // If the current character isn\'t already a child of the current node, add it\n            node.children.putIfAbsent(ch, new TrieNode());\n            \n            // Move to the child node corresponding to the current character\n            node = node.children.get(ch);\n            \n            // Increment the count to signify that this node has been visited\n            node.count++;\n        }\n    }\n\n    // Method to get the sum of scores for all prefixes of a given word\n    public int getPrefixScoreSum(String word) {\n        TrieNode node = root; // Start at the root node\n        int scoreSum = 0; // Initialize the sum of prefix scores\n        \n        // Loop through each character in the word\n        for (char ch : word.toCharArray()) {\n            // Move to the child node corresponding to the current character\n            node = node.children.get(ch);\n            \n            // Add the count of the current node to the score sum\n            scoreSum += node.count;\n        }\n        \n        // Return the total sum of scores for all prefixes of the word\n        return scoreSum;\n    }\n}\n\n// Solution class that solves the problem using the Trie\nclass Solution {\n    // Method to calculate the sum of prefix scores for each word in the array\n    public int[] sumPrefixScores(String[] words) {\n        Trie trie = new Trie(); // Create a new Trie\n\n        // Insert all words from the array into the Trie\n        for (String word : words) {\n            trie.insert(word);\n        }\n\n        // Create an array to store the result (sum of prefix scores for each word)\n        int[] result = new int[words.length];\n        \n        // Calculate the sum of prefix scores for each word\n        for (int i = 0; i < words.length; i++) {\n            result[i] = trie.getPrefixScoreSum(words[i]);\n        }\n\n        // Return the result array\n        return result;\n    }\n}\n\n```\n```JavaScript []\n// Definition of the TrieNode class, which represents a node in the Trie.\nclass TrieNode {\n    constructor() {\n        // \'children\' stores the next character nodes in the Trie.\n        // It is an object (hashmap) where each key is a character and the value is another TrieNode.\n        this.children = {};\n        // \'count\' keeps track of how many times this node has been visited during insertions.\n        this.count = 0;\n    }\n}\n\n// Definition of the Trie class, which encapsulates the root node and Trie operations.\nclass Trie {\n    constructor() {\n        // Initialize the root node of the Trie as an empty TrieNode.\n        this.root = new TrieNode();\n    }\n\n    // Method to insert a word into the Trie.\n    insert(word) {\n        // Start traversing from the root of the Trie.\n        let node = this.root;\n\n        // Traverse each character in the word.\n        for (let ch of word) {\n            // If the current character is not already a child of the current node, create a new TrieNode.\n            if (!node.children[ch]) {\n                node.children[ch] = new TrieNode();\n            }\n            // Move to the next node (child node corresponding to the current character).\n            node = node.children[ch];\n            // Increment the count for this node, as this prefix (or part of it) has been inserted.\n            node.count++;\n        }\n    }\n\n    // Method to get the sum of scores for all prefixes of the given word.\n    getPrefixScoreSum(word) {\n        // Start from the root node of the Trie.\n        let node = this.root;\n        // Variable to accumulate the score (sum of counts for each prefix).\n        let scoreSum = 0;\n\n        // Traverse each character in the word to compute the prefix scores.\n        for (let ch of word) {\n            // Move to the next node corresponding to the current character.\n            node = node.children[ch];\n            // Add the count of this node to the score sum (count represents how many times this prefix was seen).\n            scoreSum += node.count;\n        }\n\n        // Return the accumulated score sum.\n        return scoreSum;\n    }\n}\n\n/**\n * Function to compute the sum of prefix scores for an array of words.\n * \n * @param {string[]} words - The list of words for which we want to calculate prefix scores.\n * @return {number[]} - An array of numbers where each element corresponds to the sum of prefix scores for a word.\n */\nvar sumPrefixScores = function(words) {\n    // Create a new Trie.\n    const trie = new Trie();\n\n    // Insert each word from the input array into the Trie.\n    for (let word of words) {\n        trie.insert(word);\n    }\n\n    // Create an array to store the results (sum of prefix scores for each word).\n    const result = [];\n\n    // For each word in the input array, calculate the sum of prefix scores.\n    for (let word of words) {\n        result.push(trie.getPrefixScoreSum(word)); // Get the prefix score sum and store it in the result array.\n    }\n\n    // Return the result array containing the sum of prefix scores for each word.\n    return result;\n};\n\n```\n```Python []\n# Class representing a node in the Trie\nclass TrieNode:\n    def __init__(self):\n        # Dictionary to hold child nodes, where keys are characters\n        self.children = {}\n        # Count to store how many times this node (prefix) is visited\n        self.count = 0\n\n# Class representing the Trie (prefix tree) structure\nclass Trie:\n    def __init__(self):\n        # The root node of the Trie\n        self.root = TrieNode()\n\n    # Method to insert a word into the Trie\n    def insert(self, word: str):\n        node = self.root  # Start from the root node\n        # Loop through each character of the word\n        for ch in word:\n            # If the character is not a child of the current node, add it\n            if ch not in node.children:\n                node.children[ch] = TrieNode()\n            # Move to the next node (child node corresponding to the character)\n            node = node.children[ch]\n            # Increment the count for the current node (this prefix)\n            node.count += 1\n\n    # Method to calculate the sum of prefix scores for a given word\n    def get_prefix_score_sum(self, word: str) -> int:\n        node = self.root  # Start from the root node\n        score_sum = 0     # Initialize score sum\n        # Loop through each character in the word\n        for ch in word:\n            # Move to the next node (child node corresponding to the character)\n            node = node.children[ch]\n            # Add the count of the current node (this prefix) to the score sum\n            score_sum += node.count\n        return score_sum\n\n# Class to solve the problem of finding prefix scores for a list of words\nclass Solution:\n    def sumPrefixScores(self, words: List[str]) -> List[int]:\n        trie = Trie()  # Initialize a new Trie instance\n        \n        # Insert all words into the Trie to build the structure\n        for word in words:\n            trie.insert(word)\n        \n        # For each word, calculate the sum of prefix scores and return the result as a list\n        return [trie.get_prefix_score_sum(word) for word in words]\n\n```\n```Go []\npackage main\n\n// TrieNode represents a single node in the Trie structure.\n// Each node contains a map of children (to track the next characters) and a count to store how many words share the prefix up to this point.\ntype TrieNode struct {\n    children map[byte]*TrieNode // Map to store the children nodes, where each key is a character (byte)\n    count    int                // Count of words sharing this prefix\n}\n\n// Trie represents the overall structure of the prefix tree.\n// It has a root node that serves as the entry point for all word insertions and prefix queries.\ntype Trie struct {\n    root *TrieNode // Root node of the Trie\n}\n\n// newTrieNode creates a new TrieNode with an empty map of children.\n// It is used to initialize new nodes during word insertion.\nfunc newTrieNode() *TrieNode {\n    return &TrieNode{children: make(map[byte]*TrieNode)} // Initialize with an empty map for children\n}\n\n// NewTrie initializes a new Trie with a root node.\n// This function is the starting point for creating a Trie structure.\nfunc NewTrie() *Trie {\n    return &Trie{root: newTrieNode()} // Create a Trie with a new root node\n}\n\n// Insert adds a word into the Trie character by character.\n// As each character is inserted, if it doesn\'t already exist in the children map, a new TrieNode is created.\nfunc (trie *Trie) Insert(word string) {\n    node := trie.root // Start from the root node of the Trie\n    // Iterate over each character in the word\n    for i := 0; i < len(word); i++ {\n        ch := word[i] // Get the current character\n        // If the character doesn\'t exist as a child node, create a new TrieNode\n        if _, exists := node.children[ch]; !exists {\n            node.children[ch] = newTrieNode() // Add a new node for the character\n        }\n        node = node.children[ch] // Move to the child node representing the current character\n        node.count++             // Increment the count to indicate how many words share this prefix\n    }\n}\n\n// GetPrefixScoreSum calculates the sum of the prefix scores for a given word.\n// The score for each prefix is the count of how many words share that prefix in the Trie.\nfunc (trie *Trie) GetPrefixScoreSum(word string) int {\n    node := trie.root // Start from the root node of the Trie\n    scoreSum := 0     // Variable to accumulate the sum of prefix scores\n    \n    // Iterate over each character in the word\n    for i := 0; i < len(word); i++ {\n        ch := word[i]        // Get the current character\n        node = node.children[ch] // Move to the child node representing the current character\n        scoreSum += node.count   // Add the count of the current node (prefix) to the score sum\n    }\n    return scoreSum // Return the total sum of prefix scores for the word\n}\n\n// sumPrefixScores calculates the sum of prefix scores for each word in the input list.\n// It uses the Trie to store the words and then computes the score for each word.\nfunc sumPrefixScores(words []string) []int {\n    trie := NewTrie() // Create a new Trie\n    \n    // Insert all words into the Trie\n    for _, word := range words {\n        trie.Insert(word) // Add each word to the Trie\n    }\n    \n    // Initialize a result array to store the prefix score sums for each word\n    result := make([]int, len(words))\n    \n    // Calculate the sum of prefix scores for each word\n    for i, word := range words {\n        result[i] = trie.GetPrefixScoreSum(word) // Compute the prefix score sum for each word\n    }\n    \n    return result // Return the array containing the prefix score sums for all words\n}\n\n```\n\n\n---\n\n# Step-by-Step Detailed Explanation\n1. **Trie Construction**: For each word in the list, we insert each character into the Trie. At each node (character), we increase the `count`, which keeps track of how many words pass through this node.\n2. **Score Calculation**: For each word, we traverse the Trie from the root for each character in the word. At each character, we accumulate the `count` stored at that node (which tells us how many words share this prefix).\n3. **Efficiency**: Using a Trie ensures that we efficiently track prefix counts and calculate scores in linear time relative to the length of the words.\n\n---\n\n![upvote cat.png](https://assets.leetcode.com/users/images/f0a59484-9a8a-44c1-a057-4f54b18e1309_1727229545.0310395.png)\n
['Array', 'String', 'Trie', 'Counting', 'Python', 'C++', 'Java', 'Go', 'Python3', 'JavaScript']