Tự động hoàn thành
Bài học 12 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.
Đây là trường hợp sử dụng kinh điển của trie: dựa vào những gì người dùng đã nhập, hãy liệt kê mọi từ đã lưu bắt đầu bằng tiền tố đó. Đi đến nút tiền tố; nếu không thể, hãy trả về danh sách rỗng. Sau đó, duyệt cây con bên dưới và thu thập mọi từ bạn tìm thấy.
Khi đi xuống trong quá trình DFS, hãy tạo từ dần bằng cách nối thêm ký tự trên cạnh bạn vừa đi qua. Mỗi khi gặp một nút có isEndOfWord là true, đường đi hiện tại là một trong những kết quả khớp.
Thử thách
Trung bìnhViết một hàm autocomplete nhận một mảng chuỗi words và một chuỗi prefix, rồi trả về danh sách các từ trong mảng bắt đầu bằng prefix.
Danh sách trả về phải theo thứ tự tăng dần (theo bảng chữ cái). Nếu không có từ nào khớp, hãy trả về một danh sách rỗng.
Bạn phải sử dụng lớp Trie (được cung cấp trong trie cùng với trienode), không dùng các kiểu dữ liệu dựng sẵn của ngôn ngữ như tập hợp, từ điển hoặc bản đồ để đếm/theo dõi.
Tự làm thử
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char l1[4096], prefix[1024];
if (!fgets(l1, sizeof(l1), stdin)) l1[0] = 0;
if (!fgets(prefix, sizeof(prefix), stdin)) prefix[0] = 0;
l1[strcspn(l1, "\r\n")] = '\0';
prefix[strcspn(prefix, "\r\n")] = '\0';
char* words[1024]; int n = 0;
char* tok = strtok(l1, " \t");
while (tok && n < 1024) { words[n++] = tok; tok = strtok(NULL, " \t"); }
int out_n = 0;
char** res = autocomplete(words, n, prefix, &out_n);
for (int i = 0; i < out_n; i++) { printf("%s", res[i]); if (i + 1 < out_n) printf(" "); }
printf("\n");
if (res) free(res);
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
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ànhTừ dài nhất trong từ điểnTách từTự luyện tập: Trình biên dịch C online