C# Solution for Sum of Prefix Scores of Strings Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires us to compute the score of each word in an array, where the score 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires us to compute the score of each word in an array, where the score is the sum of how many words have each prefix of the word. A brute force approach (checking each prefix of each word against all other words) would be too slow, especially for large input sizes.\n\nThe key observation is that multiple words may share common prefixes, so storing and counting these shared prefixes efficiently can drastically improve performance. The Trie (Prefix Tree) is ideal for this since it allows us to store prefixes in a hierarchical structure, making prefix lookups and counting efficient.\n\nBy inserting each word into a Trie, we can track how many words share the same prefix. This allows us to quickly calculate the score for any word by simply summing the counts stored at each node along the path of the word in the Trie.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tTrie Data Structure:\n\t\u2022\tEach node in the Trie represents a character of a word, and the path from the root to a node represents a prefix of some word(s).\n\t\u2022\tEach node has a count value that tracks how many words share the prefix represented by the path to that node.\n2.\tSteps:\n\t\u2022\tInsert all words into the Trie:\n\t    \u2022\tFor each word, we insert its characters into the Trie. As we traverse the Trie, we increment the count at each node to track how many words pass through that prefix.\n\t\u2022\tCalculate the score of each word:\n\t    \u2022\tFor each word, traverse the Trie from the root node to the node representing the last character of the word. Sum up the count values at each node along the way to get the total score for the word.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n1.\tTrie Construction:\n\t\u2022\tInserting a word into the Trie takes time proportional to its length. If there are n words and the average word length is m, then:\n\t    \u2022\tInserting all words:  O(n x m) \n\t    \u2022\tThis is because for each word, we insert its m characters into the Trie, and we do this for all n words.\n2.\tScore Calculation:\n\t\u2022\tFor each word, calculating its score requires traversing its characters in the Trie, which takes  O(m)  time per word.\n\t\u2022\tFor n words, the total time to calculate scores is  O(n x m) .\n\nThus, the overall time complexity is: O(n x m)\nWhere:\n\u2022\t n  is the number of words in the input list.\n\u2022\t m  is the average length of the words.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n1.\tTrie Storage:\n\t\u2022\tThe Trie stores characters for all the words. In the worst case, if there are no shared prefixes, the Trie could contain  O(n x m)  nodes (one for each character of each word).\n\t\u2022\tEach node also contains a count field and a dictionary (or equivalent structure) to store its children.\n\nThus, the space complexity for the Trie is: O(n x m)\n\n2.\tResult Array:\n\t\u2022\tWe need an array of size n to store the results, which has a space complexity of  O(n) .\n\nThus, the total space complexity is: O(n x m)\n\n\n# Code\n```csharp []\npublic class Solution {\n    public class TrieNode {\n        public Dictionary<char, TrieNode> Children;\n        public int Count; // keeps track of how many words share this prefix\n        \n        public TrieNode() {\n            Children = new Dictionary<char, TrieNode>();\n            Count = 0;\n        }\n    }\n\n    private void Insert(TrieNode root, string word) {\n        TrieNode currentNode = root;\n        foreach (char c in word) {\n            if (!currentNode.Children.ContainsKey(c)) {\n                currentNode.Children[c] = new TrieNode();\n            }\n            currentNode = currentNode.Children[c];\n            currentNode.Count++;  // increase the prefix count\n        }\n    }\n\n    private int GetScore(TrieNode root, string word) {\n        TrieNode currentNode = root;\n        int score = 0;\n        foreach (char c in word) {\n            currentNode = currentNode.Children[c];\n            score += currentNode.Count;\n        }\n        return score;\n    }\n    public int[] SumPrefixScores(string[] words) {\n        TrieNode root = new TrieNode();\n        \n        // Step 1: Insert all words into the Trie\n        foreach (string word in words) {\n            Insert(root, word);\n        }\n        \n        // Step 2: Calculate the score for each word\n        int[] result = new int[words.Length];\n        for (int i = 0; i < words.Length; i++) {\n            result[i] = GetScore(root, words[i]);\n        }\n        \n        return result;\n    }\n}\n```
['C#']