Đếm từ có tiền tố

Bài học 11 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.

Có bao nhiêu từ đã lưu bắt đầu bằng một tiền tố (prefix) cho trước? Sau khi chèn từng từ, hãy đi từ nút gốc theo tiền tố, mỗi lần một ký tự. Nếu thiếu bất kỳ ký tự nào, đáp án là 0, không thể có từ nào bắt đầu bằng tiền tố đó.

Nếu đi đến cuối tiền tố, bạn sẽ đến một nút. Mọi từ đã lưu bắt đầu bằng tiền tố này đều nằm đâu đó trong cây con bắt nguồn từ nút đó. Hãy đếm chúng bằng cách đi qua cây con và cộng 1 cho mỗi nút có isEndOfWord là true.

Thử thách

Dễ

Viết một hàm countWordsWithPrefix nhận một mảng chuỗi words và một chuỗi prefix, rồi trả về số từ trong mảng bắt đầu bằng tiền tố đã cho.

Tiền tố rỗng khớp với mọi từ.

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 có 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"); }
    printf("%d\n", countWordsWithPrefix(words, n, prefix));
    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ếm Bắt đầu bằng Xó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