题解 | #字典树的实现#

#
# 
# @param operators string字符串二维数组 the ops
# @return string字符串一维数组
#


class Solution:
    def __init__(self):
        self.mark = {} 

    def trieU(self , operators ):
        res = []
        for operator in operators:
            if operator[0] == '1':
                self.insert(operator[1],self.mark)
            elif operator[0] == '2':
                self.delete(operator[1],self.mark)
            elif operator[0] == '3':
                contains = 'YES' if self.search(operator[1]) else 'NO'
                res.append(contains)
            elif operator[0] == '4':
                num = self.prefixNumber(operator[1])
                res.append(str(num))
#             print(self.mark)
        return res



    def search(self,word):
        if not word:
            return True
        root = self.mark
        for c in word:
            if c not in root:
                return False
            root = root[c]
        return '#' in root




    def prefixNumber(self,word):
        if not word:
            return 0
        root = self.mark

        for c in word:
            if c not in root:
                return False
            root = root[c]
        def count(root):
            res = 0
            for k,v in root.items():
                if k=='#':
                    res += 1
                else:
                    res += count(v)
            return res
        return count(root)


    def insert(self,word,root):
        if not word:
            root['#'] = {}
            return root
        c = word[0]
        root[c] = self.insert(word[1:], root.get(c,{}))
        return root



    def delete(self,word,root):
#         print(word,root)
        if not word :
            if '#' in root:
                root.pop('#')
#             print(root)
            return root
        c = word[0]
        if c not in root:
            return root
        root[c] = self.delete(word[1:], root.get(c,{}))
        return root