Trie( Prefix Tree)。
题目 Implement a trie with insert, search, and startsWith methods 思路 trie还是很有趣的,最开始我没弄清楚,以为a->b 再插入abc是
b / a->b->c
正确的应该在每个节点设一个ISKEY 来判断当前前缀是否是存储的一个str。 最开始我用的列表来存children,也不好, 用字典来存,函数实现就更简洁,而且访问效率高。 代码里后面一些是调试用的,在leetcode上提交应去掉
class node: def __init__(self,val = None): self.val = val self.isKey = False self.children = {} def __getitem__(self,i): return self.children[i] def __iter__(self): return iter(self.children.keys()) def __setitem__(self,i,x): self.children[i] = x def __bool__(self): return self.children!={} def __str__(self): return 'val: ' str(self.val) '\nchildren: ' ' '.join(self.children.keys()) def __repr__(self): return str(self) class Trie(object): def __init__(self): self.root=node('') self.dic ={'insert':self.insert,'startsWith':self.startsWith,'search':self.search} def insert(self, word): """ Inserts a word into the trie. :type word: str :rtype: void """ if not word:return nd = self.root for i in word: if i in nd: nd = nd[i] else: newNode= node(i) nd[i] = newNode nd = newNode else:nd.isKey = True def search(self, word): """ Returns if the word is in the trie. :type word: str :rtype: bool """ nd = self.root for i in word: if i in nd: nd = nd[i] else:return False else:return nd.isKey def startsWith(self, prefix): """ Returns if there is any word in the trie that starts with the given prefix. :type prefix: str :rtype: bool """ nd = self.root for i in prefix: if i in nd: nd= nd[i] else:return False return True def display(self): print('preOrderTraverse data of the Trie') self.preOrder(self.root,'') def preOrder(self,root,s): s=s root.val if root.isKey: print(s) for i in root: self.preOrder(root[i],s) if __name__=='__main__': t = Trie() rsts = [None,None,None,None,None,None,False,True,False,False,False,False,False,True,True,False,True,True,False,False,False,True,True,True] op = ["insert","insert","insert","insert","insert","insert","search","search","search","search","search","search","search","search","search","startsWith","startsWith","startsWith","startsWith","startsWith","startsWith","startsWith","startsWith","startsWith"] data = [["app"],["apple"],["beer"],["add"],["jam"],["rental"],["apps"],["app"],["ad"],["applepie"],["rest"],["jan"],["rent"],["beer"],["jam"],["apps"],["app"],["ad"],["applepie"],["rest"],["jan"],["rent"],["beer"],["jam"]] for i,datum,rst in zip(op,data,rsts): if t.dic[i](datum[0]) != rst:print(i,datum[0],rst) t.display()