Mô phỏng thuật toán Cây tiền tố · theo tiền tố

Trie · Prefix · Nhóm: Cấu trúc dữ liệu

Tìm theo tiền tố trên cây tiền tố: chỉ cần đi hết các ký tự của tiền tố, nếu tới được thì mọi từ trong cây con phía dưới đều bắt đầu bằng tiền tố đó.

Ý tưởng

Bắt đầu từ gốc, đi theo lần lượt từng ký tự của tiền tố.

Nếu thiếu cạnh cho một ký tự thì không có từ nào bắt đầu bằng tiền tố này.

Đi hết tiền tố, toàn bộ cây con tính từ nút đang đứng chính là các từ mang tiền tố đó.

Vì sao đúng

Khác với tra cứu từ, tìm tiền tố không cần nút hết-từ; chỉ cần tới được nút cuối của tiền tố là đủ để khẳng định có từ mang tiền tố đó.

Mã Python

def starts_with(root, prefix):
    node = root
    for ch in prefix:
        if ch not in node.children:
            return False
        node = node.children[ch]
    return True  # every word in the subtree has this prefix

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.