type TrieTree struct {
    pass  int
    end   int
    nexts map[string]*TrieTree
}

func NewTrieTree() *TrieTree {
    return &TrieTree{
        pass:  0,
        end:   0,
        nexts: make(map[string]*TrieTree, 32),
    }
}

func (t *TrieTree) insert(word string) {
    if word == "" {
        return
    }
    strs := strings.Split(word, "")
    node := t
    node.pass++
    for _, str := range strs {
        if _, exit := node.nexts[str]; !exit {
            node.nexts[str] = NewTrieTree()
        }
        node = node.nexts[str]
        node.pass++
    }
    node.end++
}

func (t *TrieTree) search(word string) int {
    if word == "" {
        return 0
    }
    strs := strings.Split(word, "")
    node := t
    for _, str := range strs {
        if _, exist := node.nexts[str]; !exist {
            return 0
        }
        node = node.nexts[str]
    }
    return node.end
}

func (t *TrieTree) delete(word string) {
    if t.search(word) != 0 {
        strs := strings.Split(word, "")
        node := t
        node.pass--
        for _, str := range strs {
            node.nexts[str].pass--
            if node.nexts[str].pass == 0 {
                node.nexts[str] = nil
                return
            }
            node = node.nexts[str]
        }
        node.end--
    }
}

func (t *TrieTree) prefixNumber(pre string) int {
    if pre == "" {
        return 0
    }
    strs := strings.Split(pre, "")
    node := t
    for _, str := range strs {
        if _, exist := node.nexts[str]; !exist {
            return 0
        }
        fmt.Println(node)
        node = node.nexts[str]
    }
    return node.pass
}