Python数据结构与算法之字典树实现方法示例

本文实例讲述了Python数据结构与算法之字典树实现方法。分享给大家供大家参考，具体如下：

class TrieTree():
  def __init__(self):
    self.root = {}
  def addNode(self,str):
    # 树中每个结点(除根节点)，包含到该结点的单词数，以及该结点后面出现字母的键
    nowdict = self.root
    for i in range(len(str)):
      if str[i] not in nowdict:  # 发现新的组合方式
        nowdict[str[i]] = {'count':0,'prefix':str[:i+1]}
      nowdict = nowdict[str[i]]  # 转移到下一个结点
    nowdict['count'] += 1
  def countWord(self,str):
    # 返回输入单词在树中出现的次数
    nowdict = self.root
    for s in str:
      if s not in nowdict:
        return 0
      nowdict = nowdict[s]  # 匹配当前结点,转下一个结点
    # 到了这一步证明单词存在
    return nowdict['count']
if __name__=="__main__":
  pass
  Text = ['b','abc','abd','bcd','abcd','efg','hii','bcd']
  t = TrieTree()
  for str in Text:
    t.addNode(str)
  print t.countWord('bcd')
>>> 2

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

赞 (0)

相关推荐

  • Python数据结构与算法之图的基本实现及迭代器实例详解

    Python数据结构与算法之图的基本实现及迭代器实例详解

    本文实例讲述了Python数据结构与算法之图的基本实现及迭代器.分享给大家供大家参考,具体如下: 这篇文章参考自<复杂性思考>一书的第二章,并给出这一章节里我的习题解答. (这书不到120页纸,要卖50块!!,一开始以为很厚的样子,拿回来一看,尼玛.....代码很少,给点提示,然后让读者自己思考怎么实现) 先定义顶点和边 class Vertex(object): def __init__(self, label=''): self.label = label def __repr__(sel

  • Python数据结构与算法之完全树与最小堆实例

    本文实例讲述了Python数据结构与算法之完全树与最小堆.分享给大家供大家参考,具体如下: # 完全树 最小堆 class CompleteTree(list): def siftdown(self,i): """ 对一颗完全树进行向下调整,传入需要向下调整的节点编号i 当删除了最小的元素后,当新增加一个数被放置到堆顶时, 如果此时不符合最小堆的特性,则需要将这个数向下调整,直到找到合适的位置为止""" n = len(self) # 当 i 节

  • Python实现简单字典树的方法

    本文实例讲述了Python实现简单字典树的方法.分享给大家供大家参考,具体如下: #coding=utf8 """代码实现了最简单的字典树,只支持由小写字母组成的字符串. 在此代码基础上扩展一下,就可以实现比较复杂的字典树,比如带统计数的,或支持更多字符的字典树, 或者是支持删除等操作. """ class TrieNode(object): def __init__(self): # 是否构成一个完成的单词 self.is_word = Fal

  • 详解字典树Trie结构及其Python代码实现

    字典树(Trie)可以保存一些字符串->值的对应关系.基本上,它跟 Java 的 HashMap 功能相同,都是 key-value 映射,只不过 Trie 的 key 只能是字符串. Trie 的强大之处就在于它的时间复杂度.它的插入和查询时间复杂度都为 O(k) ,其中 k 为 key 的长度,与 Trie 中保存了多少个元素无关.Hash 表号称是 O(1) 的,但在计算 hash 的时候就肯定会是 O(k) ,而且还有碰撞之类的问题:Trie 的缺点是空间消耗很高. 至于Trie树的实现

  • Python数据结构与算法之图结构（Graph）实例分析

    Python数据结构与算法之图结构（Graph）实例分析

    本文实例讲述了Python数据结构与算法之图结构(Graph).分享给大家供大家参考,具体如下: 图结构(Graph)--算法学中最强大的框架之一.树结构只是图的一种特殊情况. 如果我们可将自己的工作诠释成一个图问题的话,那么该问题至少已经接近解决方案了.而我们我们的问题实例可以用树结构(tree)来诠释,那么我们基本上已经拥有了一个真正有效的解决方案了. 邻接表及加权邻接字典 对于图结构的实现来说,最直观的方式之一就是使用邻接列表.基本上就是针对每个节点设置一个邻接列表.下面我们来实现一个最简

  • Python数据结构与算法之链表定义与用法实例详解【单链表、循环链表】

    本文实例讲述了Python数据结构与算法之链表定义与用法.分享给大家供大家参考,具体如下: 本文将为大家讲解: (1)从链表节点的定义开始,以类的方式,面向对象的思想进行链表的设计 (2)链表类插入和删除等成员函数实现时需要考虑的边界条件, prepend(头部插入).pop(头部删除).append(尾部插入).pop_last(尾部删除) 2.1 插入: 空链表 链表长度为1 插入到末尾 2.2 删除 空链表 链表长度为1 删除末尾元素 (3)从单链表到单链表的一众变体: 带尾节点的单链表

  • Python数据结构与算法之二叉树结构定义与遍历方法详解

    本文实例讲述了Python数据结构与算法之二叉树结构定义与遍历方法.分享给大家供大家参考,具体如下: 先序遍历,中序遍历,后序遍历 ,区别在于三条核心语句的位置 层序遍历  采用队列的遍历操作第一次访问根,在访问根的左孩子,接着访问根的有孩子,然后下一层 自左向右一一访问同层的结点 # 先序遍历 # 访问结点,遍历左子树,如果左子树为空,则遍历右子树, # 如果右子树为空,则向上走到一个可以向右走的结点,继续该过程 preorder(t): if t: print t.value preorde

  • Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例

    本文实例讲述了Python数据结构与算法之图的最短路径(Dijkstra算法).分享给大家供大家参考,具体如下: # coding:utf-8 # Dijkstra算法--通过边实现松弛 # 指定一个点到其他各顶点的路径--单源最短路径 # 初始化图参数 G = {1:{1:0, 2:1, 3:12}, 2:{2:0, 3:9, 4:3}, 3:{3:0, 5:5}, 4:{3:4, 4:0, 5:13, 6:15}, 5:{5:0, 6:4}, 6:{6:0}} # 每次找到离源点最近的一个顶

  • Python数据结构与算法之列表（链表，linked list）简单实现

    Python 中的 list 并不是我们传统(计算机科学)意义上的列表,这也是其 append 操作会比 insert 操作效率高的原因.传统列表--通常也叫作链表(linked list)--通常是由一系列节点(node)来实现的,其每一个节点(尾节点除外)都持有一个指向下一个节点的引用. 其简单实现: class Node: def __init__(value, next=None): self.value = value self.next = next 接下来,我们就可使用链表的结构来

  • Python数据结构与算法之字典树实现方法示例

    本文实例讲述了Python数据结构与算法之字典树实现方法.分享给大家供大家参考,具体如下: class TrieTree(): def __init__(self): self.root = {} def addNode(self,str): # 树中每个结点(除根节点),包含到该结点的单词数,以及该结点后面出现字母的键 nowdict = self.root for i in range(len(str)): if str[i] not in nowdict: # 发现新的组合方式 nowdi

  • Python cookbook（数据结构与算法）字典相关计算问题示例

    本文实例讲述了Python cookbook(数据结构与算法)字典相关计算问题.分享给大家供大家参考,具体如下: 问题:在字典上对数据执行各式各样的计算(比如求最小值.最大值.排序). 解决方案:利用zip()将字典的键-值对"反转"为值-键对序列. 例如:如下字典存放的股票名称和对应的价格: >>> prices = { 'ACME': 45.23, 'AAPL': 612.78, 'IBM': 205.55, 'HPQ': 37.20, 'FB': 10.75 }

  • Python简单定义与使用字典dict的方法示例

    Python简单定义与使用字典dict的方法示例

    本文实例讲述了Python简单定义与使用字典的方法.分享给大家供大家参考,具体如下: #coding=utf8 print ''''' Python中的字典映射数据类型是由键值对构成. python中字典一般以数字或者字符串作为键. Python中字典的值可以是任意类型的Python对象,字典元素用大括号{}包裹. ''' dicDefine={ 'Name':'ewang', 'Age': 28, 'Sex': 'famale', 'BirthDay':'1998/09/1' } print

  • Python数据结构之双向链表的定义与使用方法示例

    Python数据结构之双向链表的定义与使用方法示例

    本文实例讲述了Python数据结构之双向链表的定义与使用方法.分享给大家供大家参考,具体如下: 和单链表类似,只不过是增加了一个指向前面一个元素的指针而已. 示意图: python 实现代码: #!/usr/bin/python # -*- coding: utf-8 -*- class Node(object): def __init__(self,val,p=0): self.data = val self.next = p self.prev = p class LinkList(obje

  • Python cookbook(数据结构与算法)从字典中提取子集的方法示例

    本文实例讲述了Python从字典中提取子集的方法.分享给大家供大家参考,具体如下: 问题:想创建一个字典,其本身是另一个字典的子集 解决方案:利用字典推导式(dictionary comprehension)可轻松解决 # example of extracting a subset from a dictionary from pprint import pprint prices = { 'ACME': 45.23, 'AAPL': 612.78, 'IBM': 205.55, 'HPQ':

  • Python数据结构之哈夫曼树定义与使用方法示例

    Python数据结构之哈夫曼树定义与使用方法示例

    本文实例讲述了Python数据结构之哈夫曼树定义与使用方法.分享给大家供大家参考,具体如下: HaffMan.py #coding=utf-8 #考虑权值的haff曼树查找效率并非最高,但可以用于编码等使用场景下 class TreeNode: def __init__(self,data): self.data=data self.left=None self.right=None self.parent=None class HaffTree: def __init__(self): sel

随机推荐