資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究用 Python 實現 Trie（字首樹）
假設我們需要構建一個 Trie 結構，並實現三個基本操作：插入 (insert())、搜尋 (search()) 和以某個字首開頭 (startsWith()) 方法。我們可以假設所有輸入都是小寫字母。例如，如果我們按如下方式呼叫這些函式，我們將看到相應的輸出
- Trie trie = new Trie()
- trie.insert(“apple”)
- trie.search(“apple”) //這將返回 true
- trie.search(“app”) //這將返回 false
- trie.startsWith(“app”) //這將返回 true
- trie.insert(“app”)
- trie.search(“app”) //這將返回 true
為了解決這個問題，我們將遵循以下步驟：
- 最初建立一個名為 child 的字典。
- insert 方法將如下所示：
- current := child
- 對於單詞中的每個字母 l：
- 如果 l 不存在於 current 中，則 current[l] := 新字典
- current := current[l]
- current[#] = 1
- search 方法將如下所示：
- current := child
- 對於單詞中的每個字母 l：
- 如果 l 不存在於 current 中，則返回 false
- current := current[l]
- 如果 current[#] = 1，則返回 true，否則返回 false
- startsWith 方法將如下所示：
- current := child
- 對於單詞中的每個字母 l：
- 如果 l 不存在於 current 中，則返回 false
- current := current[l]
- 返回 True
讓我們看看下面的實現來更好地理解：
示例
class Trie(object):
def __init__(self):
self.child = {}
def insert(self, word):
current = self.child
for l in word:
if l not in current:
current[l] = {}
current = current[l]
current['#']=1
def search(self, word):
current = self.child
for l in word:
if l not in current:
return False
current = current[l]
return '#' in current
def startsWith(self, prefix):
current = self.child
for l in prefix:
if l not in current:
return False
current = current[l]
return True
ob1 = Trie()
ob1.insert("apple")
print(ob1.search("apple"))
print(ob1.search("app"))
print(ob1.startsWith("app"))
ob1.insert("app")
print(ob1.search("app"))輸入
ob1 = Trie()
ob1.insert("apple")
print(ob1.search("apple"))
print(ob1.search("app"))
print(ob1.startsWith("app"))
ob1.insert("app")
print(ob1.search("app"))輸出
True False True True
更新於: 2020年5月4日
5K+ 瀏覽量
廣告