字典树的实现

class TreeNode:
    def __init__(self):
        self.passn = 0
        self.isend = 0
        self.nextn = [None] * 26


class Solution:
    def trieU(self , operators ):
        # write code here
        if operators == []:
            return []
        root = TreeNode()
        res = []
        for opts in operators:
            opt, s = opts
            if opt == '1':
                self.insert(root, s)
            elif opt == '2':
                self.delete(root, s)
            elif opt == '3':
                res.append(self.search(root, s))
            else:
                res.append(self.prefixNumber(root, s))
        return res

    
    def insert(self, root, word):
        sl = len(word)
        i = 0
        while i < sl:
            node = root.nextn[ord(word[i]) - ord('a')]
            if node:
                node.passn += 1
                root = node
            else:
                node = TreeNode()
                node.passn += 1
                root.nextn[ord(word[i]) - ord('a')] = node
                root = node
            i += 1
        root.isend += 1
        
        
    def delete(self, root, word):
        sl = len(word)
        i = 0
        while i < sl:
            node = root.nextn[ord(word[i]) - ord('a')]
            node.passn -= 1
            root = node
            i += 1
        root.isend -= 1
    
    
    def search(self, root, word):
        sl = len(word)
        i = 0
        while i < sl:
            node = root.nextn[ord(word[i]) - ord('a')]
            root = node
            if root == None:
                return 'NO'
            i += 1
        if root != None and root.isend > 0 and i == sl:
            return 'YES'
        else:
            return 'NO'
    
    
    def prefixNumber(self, root, pre):
        sl = len(pre)
        i = 0
        while i < sl:
            node = root.nextn[ord(pre[i]) - ord('a')]
            if node == None:
                break
            root = node
            i += 1
        return root.passn if i == sl else 0

使用defaultdict和魔法方法getitem和contains

from collections import defaultdict
class Trie:
    def __init__(self):
        self.chars = defaultdict(Trie)
        self.word_num = 0
        self.pre_num = 0

    def __getitem__(self, k):
        return self.chars[k]

    def __contains__(self, k):
        return k in self.chars

    def insert(self, word):
        cur = self
        for ch in word:
            cur[ch].pre_num += 1
            cur = cur[ch]
        cur.word_num += 1

    def delete(self, word):
        cur = self
        for ch in word:
            cur[ch].pre_num -= 1
            cur = cur[ch]
        cur.word_num -= 1

    def search(self, word):
        cur = self
        for ch in word:
            cur = cur[ch]
        return cur.word_num > 0

    def prefixNumber(self, pre):
        cur = self
        for ch in pre:
            cur = cur[ch]
        return cur.pre_num

class Solution:
    def trieU(self , operators ):
        # write code here
        trie = Trie()
        res = []
        for op, t in operators:
            if op == "1":
                trie.insert(t)
            elif op == "2":
                trie.delete(t)
            elif op == "3":
                res.append("YES" if trie.search(t) else "NO")
            elif op == "4":
                res.append(trie.prefixNumber(t))
        return res