How hard is LeetCode 2416. Sum of Prefix Scores of Strings?

LeetCode 2416. Sum of Prefix Scores of Strings is rated Hard on LeetCode.

What is the time complexity of LeetCode 2416. Sum of Prefix Scores of Strings?

The Python solution on this page runs in O(total characters).

What is the space complexity of LeetCode 2416. Sum of Prefix Scores of Strings?

The Python solution on this page uses O(total characters) auxiliary space.

What topics does LeetCode 2416. Sum of Prefix Scores of Strings cover?

LeetCode 2416. Sum of Prefix Scores of Strings is tagged Trie, Array, String and Counting on LeetCode.

Sum of Prefix Scores of Strings — LeetCode 2416 Python Solution

HardTrieArrayStringCounting

Problem: #2416
Pattern: Trie
Reading time: 6 min
Source: leetcode.com

The problem

You are given an array words of size n consisting of non-empty strings. We define the score of a string term as the number of strings words[i] such that term is a prefix of words[i].

Example

Input: words = ["abc","ab","bc","b"]
Output: [5,4,3,2]
Explanation: The answer for each string is the following:

Python solution

Python

class Trie:
    __slots__ = "children", "cnt"

    def __init__(self):
        self.children = [None] * 26
        self.cnt = 0

    def insert(self, w):
        node = self
        for c in w:
            idx = ord(c) - ord("a")
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
            node.cnt += 1

    def search(self, w):
        node = self
        ans = 0
        for c in w:
            idx = ord(c) - ord("a")
            if node.children[idx] is None:
                return ans
            node = node.children[idx]
            ans += node.cnt
        return ans


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

Complexity

Measure	Complexity
Time	O(total characters)
Space	O(total characters) auxiliary

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 2416. Sum of Prefix Scores of Strings is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Trie.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2416. Sum of Prefix Scores of Strings?: LeetCode 2416. Sum of Prefix Scores of Strings is rated Hard on LeetCode.
What is the time complexity of LeetCode 2416. Sum of Prefix Scores of Strings?: The Python solution on this page runs in O(total characters).
What is the space complexity of LeetCode 2416. Sum of Prefix Scores of Strings?: The Python solution on this page uses O(total characters) auxiliary space.
What topics does LeetCode 2416. Sum of Prefix Scores of Strings cover?: LeetCode 2416. Sum of Prefix Scores of Strings is tagged Trie, Array, String and Counting on LeetCode.