Dcc 25/09/2024 || Trie 🔥
Intuition:\nThe problem involves calculating the sum of prefix scores for each word in an array of words. The prefix score of a word is determined by the number
### Intuition:\nThe problem involves calculating the sum of prefix scores for each word in an array of words. The prefix score of a word is determined by the number of times its prefixes appear across all the words in the list.\n\nA **Trie** (prefix tree) is well-suited for problems involving prefixes because it allows efficient storage and retrieval of shared prefixes among different words. The key idea is to:\n1. **Insert each word into the Trie**: As we insert a word, we increment a `countPrefix` value at each node corresponding to each character of the word. This keeps track of how many words pass through this character.\n2. **Compute the prefix score**: For each word, we traverse its prefix characters in the Trie and sum up the `countPrefix` values. This gives us the total prefix score, as it reflects how many times each prefix of the word appears in the Trie.\n\n### Approach:\n1. **Insert all words into the Trie**:\n   - While inserting each word, increment the `countPrefix` at each node for each character of the word. This tracks how many words share the same prefix.\n   \n2. **Calculate prefix scores for each word**:\n   - For each word, traverse the Trie from the root to the nodes corresponding to each character of the word.\n   - Sum the `countPrefix` values along the way, which gives the total prefix score for the word.\n\n### Step-by-step breakdown:\n- **Insertion**:\n  - For each word, traverse the Trie character by character.\n  - If a character is not present, create a new node for it and increment the `countPrefix` for that node.\n  \n- **Prefix score calculation**:\n  - For each word, traverse the Trie again, summing up the `countPrefix` values for each character of the word.\n  - The total sum gives the prefix score for the word.\n\n### Time Complexity:\n#### Insertion:\n- For each word of length \\( L \\), it takes \\( O(L) \\) to insert the word into the Trie.\n- If there are \\( N \\) words and the average word length is \\( L \\), the total time for insertion is \\( O(N * L) \\).\n\n#### Prefix score calculation:\n- For each word, calculating the prefix score requires traversing its characters in the Trie. This operation takes \\( O(L) \\) for a word of length \\( L \\).\n- Therefore, for \\( N \\) words with an average length of \\( L \\), the total time for prefix score calculation is \\( O(N * L) \\).\n\n### Overall Time Complexity:\nThe total time complexity is \\( O(N * L) \\), where \\( N \\) is the number of words and \\( L \\) is the average length of the words. This is efficient for problems with multiple words and shared prefixes, as each word is processed once during insertion and once during score calculation.\n\n### Space Complexity:\n- The space complexity is dominated by the Trie structure, which has at most \\( 26 * L * N \\) nodes (where \\( 26 \\) is the size of the alphabet, \\( L \\) is the maximum length of a word, and \\( N \\) is the number of words).\n- Therefore, the space complexity is \\( O(26 * N * L) \\), which simplifies to \\( O(N * L) \\), as 26 is a constant factor.\n\n### Summary:\n- **Time Complexity**: \\( O(N * L) \\)\n- **Space Complexity**: \\( O(N * L) \\)\n\nThis approach efficiently computes the prefix scores by leveraging the Trie data structure, which reduces redundant operations and makes it feasible to handle large datasets.\n\n# Code\n```java []\nclass Node{\n    Node[] links = new Node[26];\n    int countPrefix=0;\n    Node(){}\n    public boolean containsKey(char c){\n        return links[c-\'a\']!=null;\n    }\n    public Node get(char c){\n        return links[c-\'a\'];\n    }\n    public void put(char c , Node node){\n        links[c-\'a\']=node;\n    }\n    public void increasePrefix(){\n        countPrefix++;\n    }\n    public int getPrefix(){\n        return countPrefix;\n    }\n}\npublic class Trie{\n    private Node root;\n    Trie(){\n        root = new Node();\n    }\n    public  void insert(String s){\n         Node node = root;\n        for(int i=0;i<s.length();i++){\n            if(!node.containsKey(s.charAt(i))){\n                node.put(s.charAt(i),new Node());\n            }\n            node = node.get(s.charAt(i));\n            node.increasePrefix();\n        }\n    }\n    public int total_prefix(String s){\n        Node node = root;\n        int total=0;\n        for(int i=0;i<s.length();i++){\n\n            if(!node.containsKey(s.charAt(i))) return 0;\n            node = node.get(s.charAt(i));\n            total+= node.getPrefix();\n        }\n        return total;\n    }\n}\nclass Solution {\n    public int[] sumPrefixScores(String[] words) {\n        Trie trie = new Trie();\n        for(int i=0;i<words.length;i++){\n            trie.insert(words[i]);\n        }\n        int[] answer = new int[words.length];\n        for(int i=0;i<words.length;i++){\n            answer[i]=trie.total_prefix(words[i]);\n        }\n        return answer;   \n    }\n}\n```
['Trie', 'Java']