AcWing 835. Trie字符串统计-python 多叉树实现    原题链接    简单

作者： 作者的头像   Felix_9 ,  2020-04-03 15:49:08 ,  所有人可见 ,  阅读 933

0


1

Python代码

其实就是二叉树变成了多叉树，写法跟二叉树完全一模一样！！

import sys
class TreeNode():
    def __init__(self):
        self.next = [None]*26
        self.val = 0

table = {'a':0,'b':1,'c':2,'d':3,'e':4,'f':5,'g':6,'h':7,'i':8,'j':9,
'k':10,'l':11,'m':12,'n':13,'o':14,'p':15,'q':16,'r':17,'s':18,'t':19,'u':20,'v':21,'w':22,'x':23,'y':24,'z':25}
root = TreeNode()
def Add(root,string):
    # string分配完则截止
    if len(string) == 0:
        root.val+=1
        return
    if root.next[table[string[0]]] == None:
        # 需要创建
        root.next[table[string[0]]] = TreeNode()
        Add(root.next[table[string[0]]],string[1:])
    else:
        # 已经存在
        Add(root.next[table[string[0]]],string[1:])

def Query(root,string):
    if len(string) == 0:
        return root.val
    if root.next[table[string[0]]] == None:
        return 0
    else:
        return Query(root.next[table[string[0]]],string[1:])

n = int(input().strip())
for _ in range(n):
    op,string = list(input().strip().split())
    if op == 'I':
        Add(root,string)
    elif op == 'Q':
        print(Query(root,string))

1 评论

用户头像
buchiyu   2021-05-31 17:59         踩      回复 
class TreeNode:
    def __init__(self):
        self.val = 0
        self.next = [None]*26

root = TreeNode()

def insert(str):
    p = root
    for ch in str:
        u = ord(ch) - ord('a')
        if p.next[u] == None:
            p.next[u] = TreeNode()
        p = p.next[u]
    p.val += 1

def query(str):
    p = root
    for ch in str:
        u = ord(ch) - ord('a')
        if p.next[u] == None: return 0
        p = p.next[u]
    return p.val

n = int(input())
while n:
    n -= 1
    opt, s = input().split()
    if (opt == 'I'):
        insert(s)
    else: print(query(s))