Efficient Partial Search Of A Trie In Python

This is a hackerrank exercise, and although the problem itself is solved, my solution is apparently not efficient enough, so on most test cases I'm getting timeouts. Here's the pro

Solution 1:

Ok, so, as it turns out, using nested dicts is not a good idea in general, because hackerrank will shove 100k strings into your program and then everything will slow to a crawl. So the problem wasn't in the parsing, it was in the storing before the parsing. Eventually I found this blogpost, their solution passes the challenge 100%. Here's the code in full:

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))