สมมติว่าเราต้องสร้างโครงสร้าง tri โดยมีการดำเนินการพื้นฐานสามอย่าง เช่น เมธอด insert(), search(), startWith() เราสามารถสรุปได้ว่าอินพุตทั้งหมดเป็นตัวพิมพ์เล็ก ตัวอย่างเช่น หากเราเรียกใช้ฟังก์ชันดังนี้ เราจะเห็นผลลัพธ์
- Trie trie =ใหม่ Trie()
- trie.insert(“apple”)
- trie.search("apple") //ค่านี้จะคืนค่าเป็น true
- trie.search(“app”) // ค่านี้จะคืนค่าเป็นเท็จ
- trie.startsWith("app") //ค่านี้จะคืนค่าเป็น true
- trie.insert(“แอพ”)
- trie.search("app") //ค่านี้จะกลับมาเป็น true
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- เริ่มแรกสร้างพจนานุกรมหนึ่งคำที่เรียกว่า child
- วิธีการแทรกจะเป็นเช่น −
- ปัจจุบัน :=ลูก
- สำหรับแต่ละตัวอักษร l ในคำ −
- ถ้า l ไม่มีอยู่ในปัจจุบัน แสดงว่าปัจจุบัน[l] :=พจนานุกรมใหม่
- ปัจจุบัน :=ปัจจุบัน[l]
- ปัจจุบัน[#] =1
- วิธีการค้นหาจะเป็นเช่น −
- ปัจจุบัน :=ลูก
- สำหรับแต่ละตัวอักษร l ในคำ −
- ถ้า l ไม่มีอยู่ในปัจจุบัน ให้คืนค่าเท็จ
- ปัจจุบัน :=ปัจจุบัน[l]
- คืนค่า true ถ้า current[#] =1 มิฉะนั้น false
- เมธอด beginWith จะเป็น −
- ปัจจุบัน :=ลูก
- สำหรับแต่ละตัวอักษร l ในคำ −
- ถ้า l ไม่มีอยู่ในปัจจุบัน ให้คืนค่าเท็จ
- ปัจจุบัน :=ปัจจุบัน[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
