Bắt đầu bằng

Bài học 7 trên 14 trong khóa học Cây tiền tố, chuỗi cấu trúc dữ liệu số 8 của Coddy.

Toàn bộ lý do tồn tại của trie là để trả lời nhanh các câu hỏi về tiền tố. startsWith kiểm tra xem bất kỳ từ nào đã lưu có bắt đầu bằng tiền tố đã cho hay không, bất kể bản thân tiền tố đó có phải là một từ đã được thêm vào hoàn chỉnh hay không.

Quá trình duyệt gần như giống hệt search: bắt đầu từ nút gốc, đi theo các nút con từng ký tự một. Nếu thiếu một ký tự trên đường đi, không có từ nào đã lưu bắt đầu bằng tiền tố đó, vì vậy hãy trả về false. Nếu bạn duyệt qua mọi ký tự mà không dừng lại, câu trả lời là true, cây con bên dưới nút đó chứa ít nhất một từ đã lưu.

Điểm khác biệt duy nhất so với search: không cần kiểm tra isEndOfWord ở cuối. Chỉ cần đi đến hết tiền tố là đủ.

Thử thách

Dễ

Thêm phương thức startsWith vào lớp Trie.

Phương thức nhận một chuỗi prefix và trả về:

true nếu có từ đã được chèn bắt đầu bằng prefix (tiền tố có thể khớp với một từ hoàn chỉnh hoặc là phần đầu của một từ dài hơn).
false nếu không.

Tự làm thử

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "trie.h"

int main() {
    Trie t;
    Trie_init(&t);
    char line[1024];
    while (fgets(line, sizeof(line), stdin)) {
        line[strcspn(line, "\r\n")] = '\0';
        char* cmd = strtok(line, " \t");
        if (!cmd) continue;
        if (strcmp(cmd, "rootIsEmpty") == 0) { printf("%s\n", TrieNode_childrenCount(t.root) == 0 ? "true" : "false"); }
        if (strcmp(cmd, "hasChild") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", t.root->children[(unsigned char)arg[0]] != NULL ? "true" : "false"); }
        if (strcmp(cmd, "insert") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_insert(&t, arg); }
        if (strcmp(cmd, "search") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_search(&t, arg) ? "true" : "false"); }
        if (strcmp(cmd, "startsWith") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_startsWith(&t, arg) ? "true" : "false"); }
    }
    return 0;
}

Tất cả bài học trong Cây tiền tố, chuỗi cấu trúc dữ liệu số 8

1Giới thiệu

Giới thiệu Trie là gì?

2Dự án Trie

Lớp TrieNode Lớp Trie Chèn Tìm kiếmBắt đầu bằngXóa Số lượng từ

3Thử thách luyện tập

Tiền tố chung dài nhất Đếm từ có tiền tố Tự động hoàn thành Từ dài nhất trong từ điển Tách từ

Tự luyện tập: Trình biên dịch C online