#coding=utf8
"""代碼實現(xiàn)了最簡單的字典樹，只支持由小寫字母組成的字符串。
在此代碼基礎(chǔ)上擴(kuò)展一下，就可以實現(xiàn)比較復(fù)雜的字典樹，比如帶統(tǒng)計數(shù)的，或支持更多字符的字典樹，
或者是支持刪除等操作。
"""
class TrieNode(object):
  def __init__(self):
    # 是否構(gòu)成一個完成的單詞
    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')

更多關(guān)于Python相關(guān)內(nèi)容可查看本站專題：《Python字典操作技巧匯總》、《Python正則表達(dá)式用法總結(jié)》、《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python Socket編程技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》、《Python入門與進(jìn)階經(jīng)典教程》及《Python文件與目錄操作技巧匯總》

希望本文所述對大家Python程序設(shè)計有所幫助。

您可能感興趣的文章:

相關(guān)文章

利用Pygame制作簡單動畫的示例詳解
Pygame是被設(shè)計用來寫游戲的python模塊集合，Pygame是在優(yōu)秀的SDL庫之上開發(fā)的功能性包。本文將利用Pygame制作簡易的動畫，感興趣的可以學(xué)習(xí)一下
2022-05-05
pytest配置文件pytest.ini的詳細(xì)使用
這篇文章主要介紹了pytest配置文件pytest.ini的詳細(xì)使用，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2021-04-04
Django給admin添加Action的步驟詳解
這篇文章主要給大家介紹了關(guān)于Django給admin添加Action的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用Django具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧
2019-05-05
Python建立Map寫Excel表實例解析
這篇文章主要介紹了Python建立Map寫Excel表實例解析，具有一定借鑒價值,需要的朋友可以參考下
2018-01-01
Python中排序函數(shù)sorted()函數(shù)的使用實例
sorted()作為Python內(nèi)置函數(shù)之一,其功能是對序列（列表、元組、字典、集合、還包括字符串）進(jìn)行排序,下面這篇文章主要給大家介紹了關(guān)于Python中排序函數(shù)sorted()函數(shù)的相關(guān)資料,需要的朋友可以參考下
2022-11-11
python requests 庫請求帶有文件參數(shù)的接口實例
今天小編就為大家分享一篇python requests 庫請求帶有文件參數(shù)的接口實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
2019-01-01
詳解Django關(guān)于StreamingHttpResponse與FileResponse文件下載的最優(yōu)方法
這篇文章主要介紹了詳解Django關(guān)于StreamingHttpResponse與FileResponse文件下載的最優(yōu)方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2021-01-01
老生常談進(jìn)程線程協(xié)程那些事兒
下面小編就為大家?guī)硪黄仙Ｕ勥M(jìn)程線程協(xié)程那些事兒。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
2017-07-07
python用ConfigObj讀寫配置文件的實現(xiàn)代碼
發(fā)現(xiàn)一個簡單而又強(qiáng)大的讀寫配置文件的lib，個人覺得最大的亮點(diǎn)在于自帶的格式校驗功能，并且支持復(fù)雜的嵌套格式，而且使用起來也相當(dāng)?shù)暮啽?/div> 2013-03-03
在Django的上下文中設(shè)置變量的方法
這篇文章主要介紹了在Django的上下文中設(shè)置變量的方法,Django是重多Python高人氣框架中最為著名的一個,需要的朋友可以參考下
2015-07-07