LeetCode Daily: Sum of Prefix Scores of Strings Solution in Java | September 25, 2024

🔍 LeetCode Problem of the Day: Sum of Prefix Scores of Strings

In today's LeetCode daily challenge, we solve the Sum of Prefix Scores of Strings problem by efficiently calculating the prefix scores for a list of words using a Trie data structure. The solution is implemented in Java.

👉 Solution: Pinned in the comments.

🌟 Problem Description:
Given a list of words, the task is to calculate the sum of prefix scores for each word. The prefix score of a word is the sum of the counts of all words that share the same prefix.

🔑 Key Points:
Trie Data Structure: Efficiently stores all the words by organizing them in a tree-like structure where each node represents a prefix.
Prefix Count Calculation: As we insert the words into the Trie, we track how many words pass through each prefix to later calculate the prefix scores.
Efficient Queries: Once the Trie is built, querying the prefix scores for each word becomes fast and efficient.

📝 Code Explanation:
Trie Insertion: Each word is inserted into the Trie, and the count for each prefix is updated as we traverse down the nodes.
Score Calculation: For each word, we traverse its prefixes in the Trie and sum the counts at each node to compute the prefix score.
Result: The final result is an array containing the prefix scores for each word in the input list.

📅 Daily Solutions: Subscribe for daily LeetCode solutions explained step-by-step in Java!

👥 Join the Community: Share your thoughts on the problem in the comments. Discuss different approaches with fellow coders. Like, share, and subscribe for more daily coding challenges!

#LeetCode #Coding #Programming #TechInterview #DailyChallenge #PrefixScores #Trie #Java

[AlgoXploration]

class Solution {
class TrieNode {
TrieNode[] children = new TrieNode[26];
int count = 0;
}

public void insert(TrieNode root, String word) {
TrieNode curr = root;
for(char c : word.toCharArray()) {
int index = c - 'a';
if(curr.children[index] == null)
curr.children[index] = new TrieNode();
curr = curr.children[index];
//Count how many words pass through this prefix
curr.count++;
}
}
public int sumPrefixScores(TrieNode root, String word) {
TrieNode curr = root;
int score = 0;
for(char c : word.toCharArray()) {
int index = c - 'a';
curr = curr.children[index];
//Add the count of this prefix
score += curr.count;
}
return score;
}
public int[] sumPrefixScores(String[] words) {
TrieNode root = new TrieNode();

//Insert all words into the trie
for(String word : words)
insert(root, word);

//Calculate scores for each word
int[] result = new int[words.length];
for(int i = 0; i < words.length; i++)
result[i] = sumPrefixScores(root, words[i]);

return result;

}
}