Giả sử chúng ta phải tạo cấu trúc trie, với ba thao tác cơ bản như phương thức insert (), search (), startedWith (). Chúng ta có thể giả định rằng tất cả các đầu vào đều là chữ thường. Ví dụ, nếu chúng ta gọi các hàm như sau, chúng ta sẽ thấy kết quả đầu ra
- Trie trie =new Trie ()
- trie.insert (“apple”)
- trie.search (“apple”) // Điều này sẽ trả về true
- trie.search (“app”) // Điều này sẽ trả về false
- trie.startsWith (“app”) // Điều này sẽ trả về true
- trie.insert (“ứng dụng”)
- trie.search (“app”) // Điều này sẽ trả về true
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Ban đầu hãy tạo một từ điển có tên là con.
- Phương thức chèn sẽ giống như -
- hiện tại:=con
- cho mỗi chữ cái l trong từ -
- nếu l không có trong hiện tại, thì hiện tại [l]:=từ điển mới
- current:=current [l]
- hiện tại [#] =1
- Phương pháp tìm kiếm sẽ giống như -
- hiện tại:=con
- cho mỗi chữ cái l trong từ -
- nếu l không có trong hiện tại, thì trả về false
- current:=current [l]
- trả về true nếu hiện tại [#] =1, ngược lại là false
- Phương thức startedWith sẽ như thế nào -
- hiện tại:=con
- cho mỗi chữ cái l trong từ -
- nếu l không có trong hiện tại, thì trả về false
- current:=current [l]
- trả về True
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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")) Đầu vào
ob1 = Trie()
ob1.insert("apple")
print(ob1.search("apple"))
print(ob1.search("app"))
print(ob1.startsWith("app"))
ob1.insert("app")
print(ob1.search("app")) Đầu ra
True False True True