在python中对trie进行有效的部分搜索

Question

这是一个hackerbank练习，尽管问题本身已经解决，但我的解决方案显然不够有效，所以在大多数测试用例中，我都会超时。问题是：

我们将制作自己的联系人应用程序！应用程序必须执行两种类型的操作：

1. add name，其中name是表示联系人名称的字符串。这必须作为新联系人存储在应用程序中
2. find partial，其中partial是表示要搜索应用程序的部分名称的字符串。它必须计算从partial开始的联系人数量，并将计数打印在新行上。给定n顺序的加法和查找操作，按顺序执行每个操作

我正在使用Tries使其工作，下面是代码：

import re
def add_contact(dictionary, contact):
_end = '_end_'
current_dict = dictionary
for letter in contact:
current_dict = current_dict.setdefault(letter, {})
current_dict[_end] = _end
return(dictionary)
def find_contact(dictionary, contact):
p = re.compile('_end_')
current_dict = dictionary
for letter in contact:
if letter in current_dict:
current_dict = current_dict[letter]
else:
return(0)
count = int(len(p.findall(str(current_dict))) / 2)
re.purge()
return(count)
n = int(input().strip())
contacts = {}
for a0 in range(n):
op, contact = input().strip().split(' ')
if op == "add":
contacts = add_contact(contacts, contact)
if op == "find":
print(find_contact(contacts, contact))

因为这个问题不需要返回partial是否匹配，而是计算所有匹配的条目，所以我找不到其他方法，只能将嵌套字典强制转换为字符串，然后计算所有_end_，我用它来表示存储的字符串。这似乎是罪魁祸首，但我找不到更好的方法来进行搜索。我如何使这项工作更快？提前谢谢。

UPD:我添加了一个实际解析树的结果计数器，但对于在线检查器来说，代码仍然太慢。有什么想法吗？

def find_contact(dictionary, contact):
current_dict = dictionary
count = 0
for letter in contact:
if letter in current_dict:
current_dict = current_dict[letter]
else:
return(0)
else:
return(words_counter(count, current_dict))
def words_counter(count, node):
live_count = count
live_node = node
for value in live_node.values():
if value == '_end_':
live_count += 1
if type(value) == type(dict()):
live_count = words_counter(live_count, value)
return(live_count)

Answer 1

好吧，事实证明，使用嵌套dicts通常不是一个好主意，因为hackerlink会将100k个字符串塞进你的程序，然后一切都会慢到爬行。所以问题不在于解析，而在于解析之前的存储。最终我找到了这篇博客文章，他们的解决方案100%通过了挑战。以下是完整的代码：

class Node:
def __init__(self):
self.count = 1
self.children = {}
trie = Node()

def add(node, name):
for letter in name:
sub = node.children.get(letter)
if sub:
sub.count += 1
else:
sub = node.children[letter] = Node()
node = sub

def find(node, data):
for letter in data:
sub = node.children.get(letter)
if not sub:
return 0
node = sub
return node.count
if __name__ == '__main__':
n = int(input().strip())
for _ in range(n):
op, param = input().split()
if op == 'add':
add(trie, param)
else:
print(find(trie, param))