208. 实现 Trie (前缀树)

[题目链接](208. 实现 Trie (前缀树) - 力扣（LeetCode）)

解题思路：前缀树，每个节点的内容：pre：经过该节点的数目；end：以该节点结尾的数目；nexts：下一条路径。前缀树有一个根节点，每次查找、插入、删除都要从这个节点开始。

• 插入时，遍历该字符串，先从根节点开始，查看nexts是否有该字符，有就复用，没有就新建，经过该节点pre就加1，结尾了end就加1。然后接着弄下一个字符，同时节点也要跟着动。
• 查找：是否有某个字符串，那么就要遍历树过程中，要有路径，同时，最终的节点的end不为0；是否有某个前缀，只需要遍历树过程中，有路径即可

代码

class Trie:

    class Node:
        def __init__(self):
            self.pre = 0
            self.end = 0
            self.nexts = {}
            

    def __init__(self):
        self.root = self.Node()
        
    def insert(self, word: str) -> None:
        cur = self.root
        for ch in word:
            if ch not in cur.nexts:
                cur.nexts[ch] = self.Node()
            cur = cur.nexts[ch]
            cur.pre += 1
        cur.end += 1
        
    def search(self, word: str) -> bool:
        cur = self.root
        for ch in word:
            if ch not in cur.nexts:
                return False
            cur = cur.nexts[ch]
        return cur.end != 0

    def startsWith(self, prefix: str) -> bool:
        cur = self.root
        for ch in prefix:
            if ch not in cur.nexts:
                return False
            cur = cur.nexts[ch]
        return True