Cài đặt Trie (Cây tiền tố) trong Python

Giả sử chúng ta phải xây dựng cấu trúc Trie với ba hoạt động cơ bản: insert(), search(), startsWith(). Ta giả định tất cả đầu vào là chữ thường. Ví dụ, nếu gọi các hàm như sau, ta sẽ thấy kết quả:

• Trie trie = new Trie()
• trie.insert("apple")
• trie.search("apple") // Trả về true
• trie.search("app") // Trả về false
• trie.startsWith("app") // Trả về true
• trie.insert("app")
• trie.search("app") // Trả về true

Để giải quyết, chúng ta làm theo các bước sau:

• Khởi tạo một từ điển con.

• Phương thức insert:

  • current := con.
  • Với mỗi ký tự l trong từ:
    • Nếu l không có trong current, current[l] := từ điển mới.
    • current := current[l].
  • current['#'] = 1 (đánh dấu kết thúc từ).

• Phương thức search:

  • current := con.
  • Với mỗi ký tự l trong từ:
    • Nếu l không có trong current, trả về false.
    • current := current[l].
  • Trả về true nếu '#' trong current, ngược lại false.

• Phương thức startsWith:

  • current := con.
  • Với mỗi ký tự l trong tiền tố:
    • Nếu l không có trong current, trả về false.
    • current := current[l].
  • Trả về True.

Ví dụ

class Trie(object):
    def __init__(self):
        self.con = {}
    
    def insert(self, tu):
        hien_tai = self.con
        for ky_tu in tu:
            if ky_tu not in hien_tai:
                hien_tai[ky_tu] = {}
            hien_tai = hien_tai[ky_tu]
        hien_tai['#'] = 1
    
    def search(self, tu):
        hien_tai = self.con
        for ky_tu in tu:
            if ky_tu not in hien_tai:
                return False
            hien_tai = hien_tai[ky_tu]
        return '#' in hien_tai
    
    def startsWith(self, tien_to):
        hien_tai = self.con
        for ky_tu in tien_to:
            if ky_tu not in hien_tai:
                return False
            hien_tai = hien_tai[ky_tu]
        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