Sum of Prefix Scores of Strings Solution in C++

Problem Description

Ah, the “Sum of Prefix Scores of Strings” problem! It’s like trying to figure out how many times you’ve heard your name called in a crowded room. You know, when you’re just minding your own business, and suddenly someone yells, “Hey, you!” and you’re left wondering if they’re talking to you or the other 50 people around.

In this problem, you’re given a list of words, and your task is to calculate the score for each word based on how many times its prefixes appear in the list. Think of it as counting how many times your name is called out in a game of charades. If your name is “Sam,” and the words are “Sam,” “Samantha,” and “Samson,” then the score for “Sam” would be 3 because it appears as a prefix in all three words.

So, if you’re ready to dive into the world of prefixes and scores, let’s get coding!

Code Solution


struct TrieNode {
  vector> children;
  int count = 0;
  TrieNode() : children(26) {}
};

class Solution {
 public:
  vector sumPrefixScores(vector& words) {
    vector ans;

    for (const string& word : words)
      insert(word);

    for (const string& word : words)
      ans.push_back(getScore(word));

    return ans;
  }

 private:
  shared_ptr root = make_shared();

  void insert(const string& word) {
    shared_ptr node = root;
    for (const char c : word) {
      const int i = c - 'a';
      if (node->children[i] == nullptr)
        node->children[i] = make_shared();
      node = node->children[i];
      ++node->count;
    }
  }

  int getScore(const string& word) {
    shared_ptr node = root;
    int score = 0;
    for (const char c : word) {
      node = node->children[c - 'a'];
      score += node->count;
    }
    return score;
  }
};

Approach

The approach used in this solution revolves around the Trie data structure. Here’s a brief breakdown:

Insertion: For each word, we traverse through its characters and insert them into the Trie. While doing this, we also keep track of how many times each node (representing a character) has been visited, which helps in calculating the prefix scores.
Score Calculation: For each word, we traverse through its characters again, summing up the counts stored in the Trie nodes. This gives us the total score for that word based on how many times its prefixes appear in the list.

Time and Space Complexity

Time Complexity: O(N * M), where N is the number of words and M is the maximum length of a word. This is because we insert each word into the Trie and then calculate the score for each 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

Imagine you’re at a party, and you overhear people calling out names. If someone shouts “Alex,” and you know there are three people named Alex, Alexandra, and Alexander, you can’t help but feel a little special. That’s exactly what this problem is about—counting how many times a name (or prefix) is called out in a crowd of words.