字符串的前缀分数和

难度: Hard

给你一个长度为 n 的数组 words ，该数组由非空字符串组成。

定义字符串 word 的分数等于以 word 作为前缀的 words[i] 的数目。

例如，如果 words = ["a", "ab", "abc", "cab"] ，那么 "ab" 的分数是 2 ，因为 "ab" 是 "ab" 和 "abc" 的一个前缀。

返回一个长度为 n 的数组 answer ，其中 answer[i] 是 words[i] 的每个非空前缀的分数总和。

注意：字符串视作它自身的一个前缀。

示例 1：

输入：words = ["abc","ab","bc","b"]
输出：[5,4,3,2]
解释：对应每个字符串的答案如下：
- "abc" 有 3 个前缀："a"、"ab" 和 "abc" 。
- 2 个字符串的前缀为 "a" ，2 个字符串的前缀为 "ab" ，1 个字符串的前缀为 "abc" 。
总计 answer[0] = 2 + 2 + 1 = 5 。
- "ab" 有 2 个前缀："a" 和 "ab" 。
- 2 个字符串的前缀为 "a" ，2 个字符串的前缀为 "ab" 。
总计 answer[1] = 2 + 2 = 4 。
- "bc" 有 2 个前缀："b" 和 "bc" 。
- 2 个字符串的前缀为 "b" ，1 个字符串的前缀为 "bc" 。 
总计 answer[2] = 2 + 1 = 3 。
- "b" 有 1 个前缀："b"。
- 2 个字符串的前缀为 "b" 。
总计 answer[3] = 2 。

示例 2：

输入：words = ["abcd"]
输出：[4]
解释：
"abcd" 有 4 个前缀 "a"、"ab"、"abc" 和 "abcd"。
每个前缀的分数都是 1 ，总计 answer[0] = 1 + 1 + 1 + 1 = 4 。

提示：

1 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] 由小写英文字母组成

Submission

运行时间: 1308 ms

内存: 202.7 MB

class Solution:
    def sumPrefixScores(self, words: List[str]) -> List[int]:
        tree = dict()
        for word in words:
            root = tree
            for x in word:
                if x in root:
                    root[x]['#'] += 1
                else:
                    root[x] = {'#': 1}
                root = root[x]
        ans = [0]*len(words)
        for i in range(len(words)):
            word = words[i]
            root = tree
            tmp = 0
            for x in word:
                tmp += root[x]['#']
                root = root[x]
            ans[i] = tmp
        return ans

Explain

这道题目可以通过使用字典树（Trie）的数据结构来高效解决。首先，构建一个字典树，其中每个节点存储了到当前节点为止的字符串前缀出现的次数。这样，当再次遍历每个单词的每个前缀时，可以直接从字典树中获取该前缀出现的次数，从而计算出每个单词的前缀分数和。具体步骤包括：1. 构建字典树，记录每个前缀出现的次数。2. 对每个单词，查询其所有前缀在字典树中的出现次数，并累加得到该单词的前缀分数和。

时间复杂度: O(n*L)

空间复杂度: O(n*L)

class Solution:
    def sumPrefixScores(self, words: List[str]) -> List[int]:
        tree = dict()
        # 构建字典树并统计前缀出现次数
        for word in words:
            root = tree
            for x in word:
                if x in root:
                    root[x]['#'] += 1
                else:
                    root[x] = {'#': 1}
                root = root[x]
        ans = [0]*len(words)
        # 计算每个单词的前缀分数和
        for i in range(len(words)):
            word = words[i]
            root = tree
            tmp = 0
            for x in word:
                tmp += root[x]['#']
                root = root[x]
            ans[i] = tmp
        return ans

Explore

在构建字典树的过程中，每次插入一个单词的字符时，都会沿着字典树的路径向下走。对于每个字符，如果该字符对应的节点已经存在，则将该节点的计数器（通常用 '#' 键来表示）增加 1，表示该前缀的出现次数增加了 1。如果该字符对应的节点不存在，则创建一个新的节点，并初始化计数器为 1。这样，每个节点的计数器都准确地表示从根节点到该节点的路径（即前缀）在所有插入的单词中出现的次数。

'#'键在字典树的节点中用于存储到达该点的路径（即前缀）在插入的所有单词中出现的次数。每次插入一个单词或前缀时，沿途访问的每个节点的'#'键的值都会增加，从而确保可以快速查询任何前缀的出现频率。

字典树天然适合处理包含重复字符的单词。即使单词由相同的字符组成，构建过程仍然是将每个字符按顺序插入字典树。对于这样的单词，字典树将形成一个单一分支的结构，每个节点代表重复字符的一个实例，并且节点的'#'键会正确统计到达该节点的前缀在所有单词中出现的次数。这保证了即使是重复字符构成的单词也能正确处理和计算前缀分数。

在理论上，如果字典树构建正确且所有需要计算前缀分数的单词都是先前已经插入到字典树中的，那么就不会出现访问未定义节点的情况。然而，如果存在试图查询未经插入的单词的前缀，这将导致尝试访问未定义的节点。为预防这种情况，可以在访问节点前增加检查，确保该节点存在。如果节点不存在，则可以停止处理当前单词并返回错误或零，或者在设计时确保所有查询的单词都已经在字典树中。