Cây tiền tố Trie phục vụ tìm kiếm và gợi ý từ

Mục tiêu kiến thức

• Cài đặt Cấu trúc dữ liệu Cây tiền tố (Trie / Prefix Tree).
• Phân biệt giữa tiền tố (prefix) và từ hoàn chỉnh (is_end_of_word).
• Đạt độ phức tạp thời gian O(L) cho mọi thao tác thêm và tìm kiếm với L là độ dài từ.

Mô tả bài toán

Hệ thống thanh tìm kiếm khóa học và tài liệu của AI Empire Academy cần một động cơ gợi ý từ (autocomplete) tốc độ cao. Khi học viên gõ từng ký tự, hệ thống phải kiểm tra xem có từ nào bắt đầu bằng tiền tố đó hay không trong thời gian dưới 1 mili-giây.

Hãy xây dựng lớp PrefixTrie với các phương thức sau:

• __init__(self): Khởi tạo cây Trie rỗng.
• insert(self, word: str) -> None: Thêm một từ word vào cây Trie.
• search(self, word: str) -> bool: Trả về True nếu từ word đã được thêm vào Trie và là một từ hoàn chỉnh, ngược lại trả về False.
• starts_with(self, prefix: str) -> bool: Trả về True nếu có bất kỳ từ nào trong Trie bắt đầu bằng chuỗi prefix, ngược lại trả về False.

Quy tắc:

• Các chuỗi chỉ chứa chữ cái tiếng Anh thường a-z.
• Chuỗi rỗng "": starts_with("") luôn trả về True.

Ràng buộc

• Độ dài mỗi từ 1 ≤ |word| ≤ 2000.
• Tổng số lượng từ thêm vào: tối đa 10⁴ từ.
• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.