C++ || Trie || Easy to Understand || Visualization
Introduction to Tries\n###### A Trie, also known as a prefix tree, is an efficient tree-like data structure used for storing and searching strings. It\'s partic
# Introduction to Tries\n###### A Trie, also known as a prefix tree, is an efficient tree-like data structure used for storing and searching strings. It\'s particularly useful for problems involving prefixes, which makes it ideal for our current challenge.\n\n**In a Trie:**\n- Each node represents a character in a string.\n- The root node is typically empty.\n- Each path from the root to a node forms a prefix of one or more strings.\n- Nodes can store additional information, such as frequency counts.\n## Why a Trie is Ideal for This Problem\n###### The "Sum of Prefix Scores of Strings" problem requires us to count the occurrences of prefixes across multiple strings efficiently. A Trie is perfect for this task because:\n\n1. **Prefix Storage:** It naturally organizes strings by their prefixes.\n2. **Efficient Searching:** It allows for quick prefix lookups.\n3. **Space Efficiency:** Common prefixes are stored only once.\n\n###### Consider the example: **`words = ["abc", "ab", "bc", "b"]`**\n###### In a Trie, these words would be stored like this:\n```\n      root\n    /      \\\n   a        b\n   |      /    \\\n   b      c     *\n   | \\    |\n   c  *   *\n   |\n   *\n```\n###### Where `*` represents the end of a word.\n# Intuition\n###### Imagine walking through the Trie for each word. As you traverse, you\'re essentially following all the prefixes of that word. If we keep a count at each node representing how many words pass through it, we can easily sum up the scores for all prefixes of a word.\n###### For instance, for **`"abc"`**:\n\n**`"a"`** is a prefix of **`2`** words\n**`"ab"`** is a prefix of **`2`** words\n**`"abc"`** is a prefix of **`1`** word\n\n###### So, the total score for **`"abc"`** would be **`2 + 2 + 1 = 5`**.\n\n# Approach\n###### Certainly. Let\'s dive deeper into how the Trie stores prefixes and their counts using the example provided: **`words = ["abc", "ab", "bc", "b"]`**.\n![image.png](https://assets.leetcode.com/users/images/03bec0a8-4e50-43ae-afe4-3352a58ac18a_1727227847.599714.png)\n\n###### Now, let\'s explain how the Trie stores prefixes and their counts using this example:\n\n1. ###### **Insertion Process:**\n   - We insert each word into the Trie, one character at a time.\n   - For each character, we either create a new node or use an existing one.\n   - We increment a counter at each node we pass through.\n\n\n2. ###### **Storing Prefixes:**\n   - Each path from the root to any node represents a prefix.\n   - The counter at each node represents how many words in our list contain the prefix up to that point.\n\n\n3. ###### **Example Walkthrough:**\n    ###### a) Inserting **`"abc"`**:\n   - Create node **`\'a\'`** with count **`1`**\n   - Create node **`\'b\'`** under **`\'a\'`** with count **`1`**\n   - Create node **`\'c\'`** under **`\'ab\'`** with count **`1`**\n\n   ###### b) Inserting **`"ab"`**:\n   - Increment count of existing **`\'a\'`** node to **`2`**\n   - Increment count of existing **`\'b\'`** node under **`\'a\'`** to **`2`**\n\n   ###### c) Inserting **`"bc"`**:\n   - Create new **`\'b\'`** node from root with count **`1`**\n   - Create **`\'c\'`** node under this **`\'b\'`** with count **`1`**\n\n   ###### d) Inserting **`"b"`**:\n   - Increment count of existing **`\'b\'`** node from root to **`2`**\n\n\n4. ###### Final Trie Structure:\n   - Root has two children: **`\'a\'`** and **`\'b\'`**\n   - **`\'a\'`** node has count **`2`** (prefix of **`"abc"`** and **`"ab"`**)\n   - **`\'b\'`** node under **`\'a\'`** has count **`2`** (prefix of **`"abc"`** and **`"ab"`**)\n   - **`\'c\'`** node under **`\'ab\'`** has count **`1`** (only in **`"abc"`**)\n   - **`\'b\'`** node from root has count **`2`** (prefix of **`"bc"`** and **`"b"`**)\n   - **`\'c`**\' node under root-level **`\'b\'`** has count **`1`** (only in **`"bc"`**)\n\n\n5. ###### Prefix Counts:\n\n   - **`"a"`** is a prefix of **`2`** words\n   - **`"ab"`** is a prefix of **`2`** words\n   - **`"abc"`** is a prefix of **`1`** word\n   - **`"b"`** is a prefix of **`2`** words\n   - **`"bc"`** is a prefix of **`1`** word\n\n###### This structure allows us to quickly compute the sum of prefix scores for each word:\n- For **`"abc": 2 + 2 + 1 = 5`**\n- For **`"ab": 2 + 2 = 4`**\n- For **`"bc": 2 + 1 = 3`**\n- For **`"b": 2`**\n\n###### By storing the counts at each node, we avoid recounting prefixes, making the solution efficient for both time and space complexity.\n\n# Complexity\n- ###### Time complexity:\n  - Building the Trie: **`O(N * L)`**, where **`N`** is the number of words and **`L`** is the average length of words.\n   - Calculating scores: **`O(N * L)`**\n   - Total: **O(N * L)**\n\n- ###### Space complexity:\n  - **O(N * L)** in the worst case, where all words are distinct.\n  - In practice, it\'s often less due to shared prefixes.\n\n# Code\n```cpp []\nstruct TrieNode {\n    int isCount; // Tracks count of prefixes at this node\n    TrieNode* child[26]; // Pointers to child nodes (for each letter \'a\' to \'z\')\n\n    // Constructor initializes count and child pointers\n    TrieNode() {\n        isCount = 0;\n        for (int i = 0; i < 26; i++) {\n            child[i] = NULL;\n        }\n    }\n};\n\nclass Trie {\nprivate:\n    TrieNode* root; // Root of the Trie\n\npublic:\n    Trie() {\n        root = new TrieNode(); // Initialize Trie root\n    }\n\n    // Inserts a word into the Trie\n    void Insert(string s) {\n        TrieNode* crawl = root;\n        for (auto ch : s) {\n            int idx = ch - \'a\';\n            if (!crawl->child[idx]) {\n                crawl->child[idx] = new TrieNode(); // Create child if it doesn\'t exist\n            }\n            crawl = crawl->child[idx];\n            crawl->isCount++; // Increment count at each node\n        }\n    }\n\n    // Solves for prefix scores for each word in words\n    vector<int> solve(vector<string>& words) {\n        vector<int> result;\n        for (auto word : words) {\n            int count = 0;\n            TrieNode* crawl = root;\n            for (auto ch : word) {\n                int idx = ch - \'a\';\n                // Thanks to [@prasflames16] for pointing out\n                // that we don\'t need a NULL check here.\n                // if(!crawl->child[idx]){\n                //     break;\n                // }\n                crawl = crawl->child[idx];\n                count += crawl->isCount; // Add count of prefixes\n            }\n            result.push_back(count);\n        }\n        return result;\n    }\n};\n\nclass Solution {\npublic:\n    vector<int> sumPrefixScores(vector<string>& words) {\n        Trie t; // Create a Trie\n        for (auto word : words) {\n            t.Insert(word); // Insert each word into the Trie\n        }\n        return t.solve(words); // Compute and return the prefix scores\n    }\n};\n\n```
['String', 'Trie', 'Counting', 'C++']