python简介版

1. 稍微复杂一点的是求前缀串的数量，这里用dfs计算以当前节点为跟的字典树中包含的所有‘#’的数量，即完整的字符串个数
2. 还需要思考的就是删除字符串，这里查找以字符串结尾的字典删掉即可
3. 这道题比LeetCode[208. 实现 Trie (前缀树)]难很多，大家可以自行练习秒掉它

class Tree:
    def __init__(self):
        self.tree = {}

    def insert(self, word):
        cur = self.tree
        for w in word:
            if w not in cur:
                cur[w] = {}
            cur = cur[w]
        cur['#'] = 1

    def delete(self, word):
        cur = self.tree
        for w in word:
            if word[-1] in cur:
                del cur[word[-1]]
                break
            cur = cur[w]

    def search(self, word):
        cur = self.tree
        for w in word:
            if w not in cur:
                return 'NO'
            cur = cur[w]
        return 'YES' if '#' in cur else 'NO'

    def dfs(self, cur):
        ans = int('#' in cur)
        for k, v in cur.items():
            if type(v) == dict:
                ans += self.dfs(v)
        return ans

    def prefixNumber(self, pre):
        cur = self.tree
        for w in pre:
            if w not in cur:
                return 0
            cur = cur[w]
        return self.dfs(cur)


class Solution:

    def trieU(self, operators):
        # write code here
        ans = []
        obj = Tree()
        for op, word in operators:

            if op == '1':
                obj.insert(word)
            elif op == '2':
                obj.delete(word)
            elif op == '3':
                ans.append(obj.search(word))
            else:
                ans.append(obj.prefixNumber(word))
        return ans