Python实现简单字典树的方法

本文实例讲述了Python实现简单字典树的方法。分享给大家供大家参考，具体如下：

#coding=utf8
"""代码实现了最简单的字典树，只支持由小写字母组成的字符串。
在此代码基础上扩展一下，就可以实现比较复杂的字典树，比如带统计数的，或支持更多字符的字典树，
或者是支持删除等操作。
"""
class TrieNode(object):
  def __init__(self):
    # 是否构成一个完成的单词
    self.is_word = False
    self.children = [None] * 26
class Trie(object):
  def __init__(self):
    self.root = TrieNode()
  def add(self, s):
    """Add a string to this trie."""
    p = self.root
    n = len(s)
    for i in range(n):
      if p.children[ord(s[i]) - ord('a')] is None:
        new_node = TrieNode()
        if i == n - 1:
          new_node.is_word = True
        p.children[ord(s[i]) - ord('a')] = new_node
        p = new_node
      else:
        p = p.children[ord(s[i]) - ord('a')]
        if i == n - 1:
          p.is_word = True
          return
  def search(self, s):
    """Judge whether s is in this trie."""
    p = self.root
    for c in s:
      p = p.children[ord(c) - ord('a')]
      if p is None:
        return False
    if p.is_word:
      return True
    else:
      return False
if __name__ == '__main__':
  trie = Trie()
  trie.add('str')
  trie.add('acb')
  trie.add('acblde')
  print trie.search('acb')
  print trie.search('ac')
  trie.add('ac')
  print trie.search('ac')

更多关于Python相关内容可查看本站专题：《Python字典操作技巧汇总》、《Python正则表达式用法总结》、《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》

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

赞 (0)

相关推荐

  • 全面了解python字符串和字典

    很多序列的方法字符串同样适用, 但是,字符串是不可变的,所以一些试图改变字符串的方法是不可用的 1 字符串格式化 1)用元组或者字典格式化字符串 format = "hello,%s.s% enough for you?" values = ('world','Hot') format % values 跟C格式化类似 2)模板字符串 string模块提供了模板字符串来格式化字符串 from string import Template s = Template(x,gloriousx

  • Python的“二维”字典 (two-dimension dictionary)定义与实现方法

    本文实例讲述了Python的"二维"字典 (two-dimension dictionary)定义与实现方法.分享给大家供大家参考,具体如下: Python 中的dict可以实现迅速查找.那么有没有像数组有二维数组一样,有二维的字典呢?比如我需要对两个关键词进行查找的时候.2D dict 可以通过 dict_2d = {'a': {'a': 1, 'b': 3}, 'b': {'a': 6}} 来建立,并通过 dict_2d['a']['b'] 来访问.但是添加一个新的 "k

  • Python数据类型详解（四）字典：dict

    一.基本数据类型 整数:int 字符串:str(注:\t等于一个tab键) 布尔值: bool 列表:list 列表用[] 元祖:tuple 元祖用() 字典:dict 注:所有的数据类型都存在想对应的类列里,元祖和列表功能一样,列表可以修改,元祖不能修改. 二.字典所有数据类型: 常用操作: 索引.新增.删除.键.值.键值对.循环.长度 class dict(object): """ dict() -> new empty dictionary dict(mappin

  • python 字典(dict)按键和值排序

    python 字典(dict)的特点就是无序的,按照键(key)来提取相应值(value),如果我们需要字典按值排序的话,那可以用下面的方法来进行: 1 下面的是按照value的值从大到小的顺序来排序. dic = {'a':31, 'bc':5, 'c':3, 'asd':4, 'aa':74, 'd':0} dict= sorted(dic.items(), key=lambda d:d[1], reverse = True) print(dict) 输出的结果: [('aa', 74),

  • Python的collections模块中的OrderedDict有序字典

    如同这个数据结构的名称所说的那样,它记录了每个键值对添加的顺序. d = OrderedDict() d['a'] = 1 d['b'] = 10 d['c'] = 8 for letter in d: print letter 输出: a b c 如果初始化的时候同时传入多个参数,它们的顺序是随机的,不会按照位置顺序存储. >>> d = OrderedDict(a=1, b=2, c=3) OrderedDict([('a', 1), ('c', 3), ('b', 2)]) 除了和

  • Python常用的内置序列结构(列表、元组、字典)学习笔记

    列表与元组 列表用大括号[]表示,元组用圆括号()表示. 列表可以修改,字符串与元组不可修改. 元组的分片还是元组,列表的分片还是列表. 1.列表方法: name=["zhang3","li4","wang5"] name.append("gou6") #添加项 name.remove("gou6") #移除第一个匹配项,也可用del name[3]来移除 name.insert(3,"gou6&

  • Python构造自定义方法来美化字典结构输出的示例

    Python构造自定义方法来美化字典结构输出的示例

    示例: 复制代码 代码如下: d = { "root": { "folder2": { "item2": None, "item1": None }, "folder1": { "subfolder1": { "item2": None, "item1": None }, "subfolder2": { "item3&

  • python操作字典类型的常用方法(推荐)

    has_key()方法可以检查字典中是否含有指定的键,如果有则返回True,否则就返回False. 语法格式: dictionary_name.has_key(key) dict1 = {'01':'yangry','02':'weild','03':'hexh','04':'huangmg'} print dict1.has_key('02') print dict1.has_key('08') #result True False 2.clear()方法 用于清除字典中所有的项,无返回值.

  • Python处理json字符串转化为字典的简单实现

    今天一个朋友给个需求: 来来 {'isOK': 1, 'isRunning': None, 'isError': None} 怎么转换成字典 好,一看就是json转化很简单,开始: import json a = "{'isOK': 1, 'isRunning': None, 'isError': None}" print json.loads(a) 死活出不来结果,还报错,查了两个小时的百度,没搞明白. 最后,直接复制网上的代码,OK,运行成功,可是把我的a变量填进去,不行,报错:开

  • 举例讲解Python中字典的合并值相加与异或对比

    字典合并值相加 在统计汇总游戏数据的时候,有些数据是是每天用字典存的,当我要对多天汇总的时候,就需要合并字典了. 如果key相同的话它们的值就相加. 不能用update方法,因为用update方法则相同的key的值会覆盖,而不是相加. 千言不如一码. def union_dict(*objs): _keys = set(sum([obj.keys() for obj in objs],[])) _total = {} for _key in _keys: _total[_key] = sum([

  • Python中遍历字典过程中更改元素导致异常的解决方法

    先来回顾一下Python中遍历字典的一些基本方法: 脚本: #!/usr/bin/python dict={"a":"apple","b":"banana","o":"orange"} print "##########dict######################" for i in dict: print "dict[%s]=" % i,

  • Python中使用bidict模块双向字典结构的奇技淫巧

    快速入门 模块提供三个类来处理一对一映射类型的一些操作 'bidict', 'inverted', 'namedbidict' >>> import bidict >>> dir(bidict) ['MutableMapping', '_LEGALNAMEPAT', '_LEGALNAMERE', '__builtins__', '__doc__', '__file__', '__name__', '__package__', 'bidict', 'inverted',

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

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

随机推荐