Python实现简单字典树的方法

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

相关文章

Python中多个数组行合并及列合并的方法总结

采用numpy快速将两个矩阵或数组合并成一个数组: import numpy as np 数组 a = [[1,2,3],[4,5,6]] b = [[1,1,1],[2,2,...

python 哈希表实现简单python字典代码实例

这篇文章主要介绍了python 哈希表实现简单python字典代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 class...

深入学习Python中的装饰器使用

装饰器 vs 装饰器模式 首先,大家需要明白的是使用装饰器这个词可能会有不少让大家担忧的地方,因为它很容易和设计模式这本书里面的装饰器模式发生混淆。曾经一度考虑给这个新的功能取一些其它的...

Python3 能振兴 Python的原因分析

我从Stephen A. Goss那读到关于了《Python 3正在毁灭Python》。这篇文章有不少精彩的论点,但我却并不认为Python 3是在毁灭Python,也不认为整个局面对P...

python如何读写json数据

本文实例为大家分享了python读写json数据的具体代码,供大家参考,具体内容如下 案例:   在web应用中常常用到json数据进行传输数据,本质上是字典类型数据转换成字符串,通过字...