Leetcode Daily Question 25/09/2024 - 2416. Sum of Prefix Scores of Strings

Problem Description:

You are given an array words of size n consisting of non-empty strings. We define the score of a string word as the number of strings words[i] such that word is a prefix of words[i]. For example, if words = ["a", "ab", "abc", "cab"], then the score of "ab" is 2, since "ab" is a prefix of both "ab" and "abc". Return an array answer of size n where answer[i] is the sum of scores of every non-empty prefix of words[i]. Note that a string is considered as a prefix of itself.

# Solution 1: Using Trie
from typing import List
class TrieNode:
  def __init__(self):
    self.children = {}
    self.isEnd = False
    self.prefixCounter = 0
  
class Trie:
  def __init__(self):
    self.root = TrieNode()
 	
  
  def insert(self, word):
    node = self.root
    for char in word:
      if char not in node.children:
        node.children[char] = TrieNode()
      
      node = node.children[char]
      node.prefixCounter += 1
    node.isEnd = True
    
  def score(self, prefix):
    node = self.root
    total = 0
    for char in prefix:
      if char not in node.children:
        break
      node = node.children[char]
      total += node.prefixCounter
    
    return total
  
  
class Solution:
  def __init__(self):
    self.trie = Trie()
    
  def sumPrefixScores(self, words: List[str]) -> List[int]:
    for word in words:
      self.trie.insert(word)
    
    return [self.trie.score(word) for word in words]
  
  

  
# Solution 2 With nested dictionary
from typing import List
class Solution:
  def sumPrefixScores(self, words: List[str]) -> List[int]:
    d = {}
    for word in words:
      depth = d
      for char in word:
        if char not in depth:
          depth[char] = [0, {}]
        depth[char][0] += 1
        depth = depth[char][1]
        
    result = []
    for word in words:
      score = 0
      depth = d
      for char in word:
        score += depth[char][0]
        depth = depth[char][1]
      result.append(score)
    
    return result

Explanation:

The idea of this question is to find efficient ways to store the number of times a prefix was encountered.

We can do this either using a Trie (prefix tree) or using nested dictionaries.

Let us explore the Trie method first. A Trie stores a word by starting at an empty root node. This represents the start of all words.

Then we traverse each word and build a path from start to end like you would in a binary tree.

If we encounter another word with the same letters, the trie would always try to reuse existing nodes to create a branch.

For example, if we have the words "cat" and "car" this is how the trie would look.

root 
 |
 c
 |
 a
 | \
 r t

With that in mind, we can then add a counter to each node to count how many time we passed through that node. This signifies the number of times the prefix occurs in amongst all the words.

Finally, we can tally up the score of each path from root to leaf to find the prefix score for that particular word.

class TrieNode:
  def __init__(self):
    self.children = {}
    self.isEnd = False
    self.prefixCounter = 0
  
  def insert(self, word):
    node = self.root
    for char in word:
      if char not in node.children:
        node.children[char] = TrieNode() # Create a new node for the child
      node = node.children[char] # move on to this node
      node.prefixCounter += 1 # We have traverse this node
    node.isEnd = True # Terminate the traversal since we have reach the end of the word
    
  def score(self, prefix):
    node = self.root
    score = 0
    for char in word:
      if char not in node.children:
        break
      node = node.children[char]
      score += node.prefixCounter
      
    return score

Then to find the prefix score for each of the word in words. We first insert it into the trie then we use the score method to calculate the prefix score.

class Solution:
  def __init__(self):
    self.trie = Trie()
    
  def sumPrefixScores(self, words: List[str]) -> List[int]:
    for word in words:
      self.trie.insert(word)
    
    return [self.trie.score(word) for word in words]

This has time complexity O(n * L), where n is the number of words in L is the average length of all words.

This has space complexity O(n * L) as we need to store all words and their subsequent children.

Now let us move on to nested dictionary. This method is in essence similar to the constructing the Trie. But instead of having to physically construct child references we can use nested dictionaries to do the same.

We use a dictionary to store the start of words as key, each key then stores a list that has
1. the number of times we have seen this prefix
2. a dictionary that stores potential children in the same way as the big dictionary.

So again using the "cat" and "car" example we have

d = {c: [2, {
      a: [2, {
        t: [1 , {}], 
        r: [1, {}]}
      ]}
    ]}

Once we have construct the nested dictionary for all the words, we get the prefix score for each word by accumulating the score at each depth.

class Solution:
  def sumPrefixScores(self, words):
    d = {}
    for word in words:
      depth = d
      for char in words:
        if char not in depth:
          depth[char] = [0, {}]
        depth[char][0] += 1
        dpeth = depth[char][1]
    
    result = []
    for word in words:
      score = 0 
      depth = d
      for char in words:
        score += depth[char][0]
        depth = depth[char][1]
      result.append(score)
        
    return result

The time complexity is again O(n * L) as we traverse each word to store each letter and references to the head.

The space complexity is also O(n * L) as we store the information about the words as we did in Trie.

However, in practice this is slightly more efficient because it has less overhead without the custom Trie class. But with large enough n and L, the difference becomes minimal.

Both solutions can be found near the top of the page.