Trie-Trie-Trie!!! - Part 2

A so-called hard problem but in reality a straightforward Trie implementation. Typical Trie where the very first element (root) is ignored and you use a hashtable for the children. In this case here keep track of the score as you add all the words. Works super fast in execution time O(sizeWord * numberWords) or 1M (max) steps. Code is down below, cheers, ACC.

Sum of Prefix Scores of Strings - LeetCode

2416. Sum of Prefix Scores of Strings

Hard

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.

 

Example 1:

Input: words = ["abc","ab","bc","b"]
Output: [5,4,3,2]
Explanation: The answer for each string is the following:
- "abc" has 3 prefixes: "a", "ab", and "abc".
- There are 2 strings with the prefix "a", 2 strings with the prefix "ab", and 1 string with the prefix "abc".
The total is answer[0] = 2 + 2 + 1 = 5.
- "ab" has 2 prefixes: "a" and "ab".
- There are 2 strings with the prefix "a", and 2 strings with the prefix "ab".
The total is answer[1] = 2 + 2 = 4.
- "bc" has 2 prefixes: "b" and "bc".
- There are 2 strings with the prefix "b", and 1 string with the prefix "bc".
The total is answer[2] = 2 + 1 = 3.
- "b" has 1 prefix: "b".
- There are 2 strings with the prefix "b".
The total is answer[3] = 2.

Example 2:

Input: words = ["abcd"]
Output: [4]
Explanation:
"abcd" has 4 prefixes: "a", "ab", "abc", and "abcd".
Each prefix has a score of one, so the total is answer[0] = 1 + 1 + 1 + 1 = 4.

 

Constraints:

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words[i] consists of lowercase English letters.

Accepted

8,830

Submissions

25,527

public class TrieScore
{
    public Hashtable children = null;
    public int score = 0;

    public TrieScore()
    {
        children = new Hashtable();
        score = 0;
    }

    public void AddWord(string word)
    {
        if (String.IsNullOrEmpty(word)) return;
        if (!children.ContainsKey(word[0])) children.Add(word[0], new TrieScore());
        TrieScore child = (TrieScore)children[word[0]];
        child.score++;
        child.AddWord(word.Substring(1));
    }

    public int WordScore(string word)
    {
        if (String.IsNullOrEmpty(word) || !children.ContainsKey(word[0])) return 0;
        TrieScore child = (TrieScore)children[word[0]];
        return child.score + child.WordScore(word.Substring(1));
    }
}

public int[] SumPrefixScores(string[] words)
{
    TrieScore trieScore = new TrieScore();
    foreach (string word in words) trieScore.AddWord(word);
    int[] retVal = new int[words.Length];
    for (int i = 0; i < retVal.Length; i++)
        retVal[i] = trieScore.WordScore(words[i]);
    return retVal;
}