Hitung Kata dengan Prefiks

Pelajaran 11 dari 14 dalam kursus Trie: Struktur Data Seri #8 di Coddy.

Berapa banyak kata yang tersimpan dimulai dengan prefiks tertentu? Setelah memasukkan setiap kata, telusuri dari akar satu karakter demi satu karakter mengikuti prefiks. Jika ada karakter yang tidak ditemukan, jawabannya nol, tidak ada kata yang mungkin dimulai dengan prefiks itu.

Jika kamu mencapai akhir prefiks, kamu akan berada di sebuah node. Setiap kata tersimpan yang dimulai dengan prefiks ini berada di suatu tempat dalam subtree yang berakar di sana. Hitung kata-kata tersebut dengan menelusuri subtree dan menambahkan 1 untuk setiap node yang memiliki isEndOfWord bernilai true.

Tantangan

Mudah

Buat fungsi countWordsWithPrefix yang menerima array string words dan string prefix, lalu mengembalikan jumlah kata dalam array yang diawali dengan prefix yang diberikan.

Prefix kosong cocok dengan setiap kata.

Kamu harus menggunakan class Trie (disediakan dalam trie bersama trienode). Jangan gunakan fitur bawaan bahasa seperti set, dict, atau map untuk menghitung atau melacak.

Coba sendiri

#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;
}

Semua pelajaran di Trie: Struktur Data Seri #8

1Pengenalan

Pengenalan Apa Itu Trie?

2Proyek Trie

class TrieNode class Trie Sisipkan Cari Diawali Dengan Hapus Jumlah Kata

3Tantangan Latihan

Prefiks Bersama TerpanjangHitung Kata dengan PrefiksPelengkapan Otomatis Kata Terpanjang dalam Dictionary Pemisahan Kata

Latihan sendiri: Compiler C online