C++ Simple Trie / Prefix Tree implementation
Intuition\n- In this problem we need to find the number of strings that has a prefix in the current string.\n- Thus when it comes to counting prefixes of string
# Intuition\n- In this problem we need to find the number of strings that has a prefix in the current string.\n- Thus when it comes to counting prefixes of strings and counting occurrences, we can rely on Trie / prefix tree data structure to efficiently store the strings and traverse through them.\n# What is Trie ?\n- A data structure that efficiently stores strings by sharing common prefixes. \n- Each node represents a character, and branches are created at points where strings diverge, allowing for quick retrieval and prefix-based searching.\n# Approach\n- We can store all the strings in a Trie using the `insert` function, which handles the following:\n\t- For each character in the string, we traverse down the Trie, creating new nodes as necessary.\n\t- Each node contains a `count` variable that keeps track of how many strings share the prefix up to that node, making it easy to find out how many strings have the same prefix.\n- Then we can iterate through all the strings in the array, and count for the number of strings has a prefix in the current string.\n\t- We do this by traversing in Trie and increment our score based on the `count` of the current node.\n# Code\n```cpp []\nstruct TrieNode {\n    TrieNode *child[26];\n    bool isEnd;\n    int count = 0;\n    TrieNode() {\n        isEnd = false;\n        count = 0;\n        for (int i = 0; i < 26; i++) child[i] = NULL;\n    }\n};\n\nvoid insert(TrieNode *root, string key) {\n    TrieNode *node = root;\n    for (char c : key) {\n        int idx = c - \'a\';\n        if (!node->child[idx]) node->child[idx] = new TrieNode();\n        node = node->child[idx];\n        node->count++;\n    }\n    node->isEnd = true;\n}\n\nint startWith(TrieNode *root, string pref) {\n    int score = 0;\n    TrieNode *node = root;\n    for (char c : pref) {\n        int idx = c - \'a\';\n        if (!node->child[idx]) break;\n        node = node->child[idx];\n        score += node->count;\n    }\n    return score;\n}\n\nclass Solution {\n  public:\n    vector<int> sumPrefixScores(vector<string> &words) {\n        TrieNode *root = new TrieNode();\n        for (auto it : words) insert(root, it);\n\n        vector<int> res;\n        for (auto it : words) res.push_back(startWith(root, it));\n        return res;\n    }\n};\n```
['String', 'Trie', 'Counting', 'C++']