Sum of Prefix Scores of Strings Solution in Java

Navigate to Other Solutions


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

class Solution {
  public int[] sumPrefixScores(String[] words) {
    int[] ans = new int[words.length];

    for (final String word : words)
      insert(word);

    for (int i = 0; i < words.length; ++i)
      ans[i] = getScore(words[i]);

    return ans;
  }

  private TrieNode root = new TrieNode();

  private void insert(String word) {
    TrieNode node = root;
    for (final char c : word.toCharArray()) {
      final int i = c - 'a';
      if (node.children[i] == null)
        node.children[i] = new TrieNode();
      node = node.children[i];
      ++node.count;
    }
  }

  private int getScore(String word) {
    TrieNode node = root;
    int score = 0;
    for (final char c : word.toCharArray()) {
      node = node.children[c - 'a'];
      score += node.count;
    }
    return score;
  }
}

Problem Description

So, you think you can just throw a bunch of words together and expect them to behave? Welcome to the world of strings, where every prefix counts! The problem at hand is to calculate the sum of prefix scores for a list of strings. Each prefix score is the number of times that prefix appears in the list of words.

Imagine you’re at a party, and you keep hearing people say “Hello” and “Hello World.” If you were to calculate the prefix score for “Hello,” it would be 2 because it appears twice. But if you were to calculate the score for “Hello W,” it would be 1 because only “Hello World” starts with that prefix.

In short, we’re counting how many times each prefix of a word appears in the list. Sounds simple, right? Well, let’s dive into the code!

Approach Explanation

The solution employs a Trie (prefix tree) to efficiently store and count the prefixes of the words. Here’s a brief rundown of the approach:

Insert Words into Trie: For each word, we traverse its characters and insert them into the Trie. Each time we insert a character, we increment a count that keeps track of how many words share that prefix.
Calculate Scores: For each word, we traverse its characters again, this time summing up the counts from the Trie to get the total prefix score.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N * M), where N is the number of words and M is the maximum length of a word.
Space Complexity	O(N * M) in the worst case, as we may need to store all characters of all words in the Trie.

Real-World Example

Think of a library where every book title is a string. If you want to know how many books start with "Harry," you would count all the titles that begin with that prefix. This is exactly what our solution does, but in a more efficient way using a Trie.