Jumlah Kata

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

Berapa banyak kata berbeda yang ada di trie ini sekarang? Tidak ada penghitung yang terus diperbarui, jadi kita harus menelusuri pohon dan menghitung node yang isEndOfWord-nya bernilai true.

Penelusuran depth-first yang dimulai dari akar dapat menyelesaikannya dalam satu kali penelusuran. Untuk setiap node, tambahkan 1 jika node tersebut menandai akhir kata, lalu lakukan rekursi ke setiap anak dan jumlahkan hasilnya. Jumlah totalnya adalah banyaknya kata yang tersimpan.

Perhatikan bahwa cara ini secara alami menangani duplikat: menyisipkan "cat" tiga kali tetap hanya menandai satu node sebagai akhir kata, sehingga hitungannya adalah 1. Prefiks yang tidak pernah disisipkan secara tersendiri juga tidak dihitung, node-nodenya memang ada, tetapi isEndOfWord-nya bernilai false.

Tantangan

Mudah

Tambahkan method wordCount ke class Trie.

Method ini tidak menerima input dan mengembalikan jumlah kata unik yang saat ini tersimpan di trie. Telusuri trie mulai dari root dan hitung setiap node yang isEndOfWord-nya bernilai true.

Coba sendiri

#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"); }
        if (strcmp(cmd, "delete") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_delete(&t, arg); }
        if (strcmp(cmd, "wordCount") == 0) { printf("%d\n", Trie_wordCount(&t)); }
    }
    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 HapusJumlah Kata

3Tantangan Latihan

Prefiks Bersama Terpanjang Hitung Kata dengan Prefiks Pelengkapan Otomatis Kata Terpanjang dalam Dictionary Pemisahan Kata

Latihan sendiri: Compiler C online