You are viewing a single comment's thread. Return to all comments →
Minimal object oriented implementation of a Trie that passes all test cases (Python 2.7)
class Node(object): __slots__ = ['prefixes','children'] def __init__(self): self.children = dict() self.prefixes = 0 class Trie(object): def __init__(self): self.root = Node() def add(self, word): node = self.root i = 0 while i < len(word): if not node.children.get(word[i]): node.children[word[i]] = Node() node = node.children[word[i]] else: node = node.children[word[i]] node.prefixes += 1 i += 1 def find(self, val): node = self.root i = 0 while i < len(val): if not node.children.get(val[i]): return 0 else: node = node.children[val[i]] i += 1 return node.prefixes a = int(raw_input()) trie = Trie() for i in range(a): b = raw_input().split() if b[0] == 'add': trie.add(b[1]) if b[0] == 'find': print trie.find(b[1])
Seems like cookies are disabled on this browser, please enable them to open this website
Contacts
You are viewing a single comment's thread. Return to all comments →
Minimal object oriented implementation of a Trie that passes all test cases (Python 2.7)