频道栏目
首页 > 资讯 > 其他 > 正文

Trie( Prefix Tree)

18-04-11        来源:[db:作者]  
收藏   我要投稿

Trie( Prefix Tree)。

  题目 Implement a trie with insert, search, and startsWith methods   思路 trie还是很有趣的,最开始我没弄清楚,以为a->b 再插入abc是

 b / a->b->c

正确的应该在每个节点设一个ISKEY 来判断当前前缀是否是存储的一个str。 最开始我用的列表来存children,也不好, 用字典来存,函数实现就更简洁,而且访问效率高。 代码里后面一些是调试用的,在leetcode上提交应去掉   

show me the code

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()
相关TAG标签
上一篇:Windows下如何更改MySQL数据库的存储位置?
下一篇:windows如何实现开机自动执行.bat脚本?
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站