Home > Backend Development > Python Tutorial > Introduction to the method of implementing a simple dictionary tree in Python

Introduction to the method of implementing a simple dictionary tree in Python

高洛峰
Release: 2017-03-06 13:42:40
Original
1432 people have browsed it

The example in this article describes how to implement a simple dictionary tree in Python. Share it with everyone for your reference, the details are as follows:

#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')
Copy after login

For more introduction on how to implement a simple dictionary tree in Python and related articles, please pay attention to the PHP Chinese website!

Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template