[数据结构与算法]LeetCode 1804. Implement Trie II (Prefix Tree) - 前缀树（Trie Tree or Prefix Tree）系列题7

A?trie?(pronounced as "try") or?prefix tree?is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie()?Initializes the trie object.
• void insert(String word)?Inserts the string?word?into the trie.
• int countWordsEqualTo(String word)?Returns the number of instances of the string?word?in the trie.
• int countWordsStartingWith(String prefix)?Returns the number of strings in the trie that have the string?prefix?as a prefix.
• void erase(String word)?Erases the string?word?from the trie.

Example 1:

Input
["Trie", "insert", "insert", "countWordsEqualTo", "countWordsStartingWith", "erase", "countWordsEqualTo", "countWordsStartingWith", "erase", "countWordsStartingWith"]
[[], ["apple"], ["apple"], ["apple"], ["app"], ["apple"], ["apple"], ["app"], ["apple"], ["app"]]
Output
[null, null, null, 2, 2, null, 1, 1, null, 0]

Explanation
Trie trie = new Trie();
trie.insert("apple");               // Inserts "apple".
trie.insert("apple");               // Inserts another "apple".
trie.countWordsEqualTo("apple");    // There are two instances of "apple" so return 2.
trie.countWordsStartingWith("app"); // "app" is a prefix of "apple" so return 2.
trie.erase("apple");                // Erases one "apple".
trie.countWordsEqualTo("apple");    // Now there is only one instance of "apple" so return 1.
trie.countWordsStartingWith("app"); // return 1
trie.erase("apple");                // Erases "apple". Now the trie is empty.
trie.countWordsStartingWith("app"); // return 0

Constraints:

• 1 <= word.length, prefix.length <= 2000
• word?and?prefix?consist only of lowercase English letters.
• At most?3 * 104?calls?in total?will be made to?insert,?countWordsEqualTo,?countWordsStartingWith, and?erase.
• It is guaranteed that for any function call to?erase, the string?word?will exist in the trie.

这题还是标准的前缀树(Trie)题，是LeetCode 208. Implement Trie (Prefix Tree)?的拓展。题目要求允许插入重复的单词，查找匹配的单词个数，查找含有指定前缀的单词个数，还有可以从树里擦除一个单词。

1）定义前缀树(Trie)数据结构，为了方便查询单词的个数，每个节点需要定义一个计数变量用于表示单词结束和单词出现次数；为了方便查询含有相同前缀的单词个数，每个节点增加一个计数变量用于统计单词经过该节点的次数即即含有该前缀的单词次数。

2）查找单词个数：标准的前缀树查找函数，从根节点开始按单词字母搜索子节点直到单词结束，返回最后一个节点的单词结束计数变量。

3）查找含有相同前缀的单词个数，由于前面定义了一个前缀计数变量使得该函数变得简单，从根节点开始按前缀字符串的字母挨个搜索子节点直到前缀字符串结束，返回最后一个节点的前缀计数变量。

4）擦除函数，由于题目的限制条件即要擦除的单词一定存在树里，使得擦除函数简单不少。从根节点开始按单词字母搜索子节点直到单词结束，每经过一个节点前缀计数减1，最后一个节点单词结束计数减1。（如果没题目限制，输入的单词可能不存在，那就会破坏树里计数变量）

class TrieNode:
    def __init__(self):
        self.startCnt = 0
        self.endCnt = 0
        self.children = [None] * 26
class Trie:

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

    def insert(self, word: str) -> None:
        node = self.root
        for c in word:
            idx = ord(c) - ord('a')
            if not node.children[idx]:
                node.children[idx] = TrieNode()
            node = node.children[idx]
            node.startCnt += 1
        node.endCnt += 1

    def countWordsEqualTo(self, word: str) -> int:
        node = self.root
        for c in word:
            idx = ord(c) - ord('a')
            if not node.children[idx]:
                return 0
            node = node.children[idx]
        return node.endCnt

    def countWordsStartingWith(self, prefix: str) -> int:
        node = self.root
        for c in prefix:
            idx = ord(c) - ord('a')
            if not node.children[idx]:
                return 0
            node = node.children[idx]
        
        return node.startCnt

    def erase(self, word: str) -> None:
        node = self.root
        for c in word:
            idx = ord(c) - ord('a')
            if not node.children[idx]:
                return 0
            node = node.children[idx]
            node.startCnt -= 1
        
        node.endCnt -= 1