进阶篇作业：《Trie》

[azl397985856]

本节的作业是第 311 场周赛的 T4 6183. 字符串的前缀分数和，官方难度为困难。 如果你熟悉前缀树，能想到这道题用前缀树的话就简单了。

[azl397985856]

这种字符串前缀题目还不上 trie? 直接魔改我插件里提供的 Trie 模板，增加一个方法 sum 统计即可。 sum 逻辑和 search 几乎一样，具体看代码

class TrieNode:
    def __init__(self):
        self.count = 0 # 表示以该处节点构成的串的个数
        self.preCount = 0 # 表示以该处节点构成的前缀的字串的个数
        self.children = {}

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
            node.preCount += 1
        node.count += 1

    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.count > 0

    def startsWith(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.preCount > 0
    def sum(self, word):
        ans = 0
        node = self.root
        for ch in word:
            node = node.children[ch]
            ans += node.preCount
        return ans
            
class Solution:
    def sumPrefixScores(self, words: List[str]) -> List[int]:
        trie = Trie()
        ans = []
        for word in words:
            trie.insert(word)
        for word in words:
            ans.append(trie.sum(word))
        return ans