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

yipeiwu_com5年前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程序设计有所帮助。

相关文章

python 实现上传图片并预览的3种方法(推荐)

python 实现上传图片并预览的3种方法(推荐)

在常见的用户注册页面,需要用户在本地选择一张图片作为头像,并同时预览。 常见的思路有两种:一是将图片上传至服务器的临时文件夹中,并返回该图片的url,然后渲染在html页面;另一种思路是...

python33 urllib2使用方法细节讲解

Proxy 的设置 urllib2 默认会使用环境变量 http_proxy 来设置 HTTP Proxy。如果想在程序中明确控制 Proxy 而不受环境变量的影响,可以使用下面的方式...

Python合并多个Excel数据的方法

Python合并多个Excel数据的方法

安装模块 1、找到对应的模块   http://www.python-excel.org/ 2、用pip install 安装 pip install xlrd p...

代码分析Python地图坐标转换

最近做项目正好需要坐标的转换 各地图API坐标系统比较与转换; WGS84坐标系:即地球坐标系,国际上通用的坐标系。设备一般包含GPS芯片或者北斗芯片获取的经纬度为WGS84地...

浅析python redis的连接及相关操作

redis简介 Redis是一个开源的使用ANSIC语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。是一个非关系型数据库,经常会用作缓...