LeetCode 2416: Sum of Prefix Scores of Strings Solution

Master LeetCode problem 2416 (Sum of Prefix Scores of Strings), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2416. Sum of Prefix Scores of Strings

Hard

Array String Trie Counting

Problem Explanation

Explanation:

We can solve this problem efficiently by iterating through each word in the array and counting the number of strings that have the current word as a prefix. We can achieve this by creating a Trie data structure where each node represents a character in the word. By traversing the Trie for each word, we can find the count of strings that have the current word as a prefix. Finally, we calculate the sum of scores for all the prefixes of each word.

Algorithm:

Create a Trie data structure to store the words.
Insert all words into the Trie.
Traverse the Trie for each word and count the number of strings with the current word as a prefix.
Calculate the sum of scores for all prefixes of each word.
Return the array of scores.

Time Complexity:

Building the Trie: O(n * m) where n is the number of words and m is the average length of a word.
Traversing the Trie for each word: O(n * m)
Overall, the time complexity is O(n * m).

Space Complexity:

Trie data structure: O(n * m)
Overall, the space complexity is O(n * m).

Solution Code

class TrieNode {
    TrieNode[] children;
    int count;
    
    public TrieNode() {
        children = new TrieNode[26];
        count = 0;
    }
}

class Solution {
    public int[] prefixScores(String[] words) {
        TrieNode root = new TrieNode();
        int[] scores = new int[words.length];
        
        for (String word : words) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                if (node.children[c - 'a'] == null) {
                    node.children[c - 'a'] = new TrieNode();
                }
                node = node.children[c - 'a'];
                node.count++;
            }
        }
        
        for (int i = 0; i < words.length; i++) {
            TrieNode node = root;
            String word = words[i];
            for (char c : word.toCharArray()) {
                node = node.children[c - 'a'];
                scores[i] += node.count;
            }
        }
        
        return scores;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2416 (Sum of Prefix Scores of Strings)?

This page provides optimized solutions for LeetCode problem 2416 (Sum of Prefix Scores of Strings) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2416 (Sum of Prefix Scores of Strings)?

The time complexity for LeetCode 2416 (Sum of Prefix Scores of Strings) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2416 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2416 in Java, C++, or Python.

Back to LeetCode Solutions