Diawali Dengan

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

Seluruh alasan keberadaan trie adalah untuk menjawab pertanyaan tentang prefiks dengan cepat. startsWith memeriksa apakah setidaknya satu kata yang tersimpan diawali dengan prefiks tertentu, tidak masalah apakah prefiks itu sendiri merupakan kata lengkap yang telah dimasukkan.

Penelusurannya hampir sama persis dengan search: mulai dari root, ikuti child satu karakter demi satu karakter. Jika ada karakter yang tidak ditemukan di sepanjang jalur, tidak ada kata tersimpan yang diawali prefiks itu, jadi kembalikan false. Jika kamu menelusuri setiap karakter tanpa berhenti, jawabannya adalah true, subtree di bawah node itu berisi setidaknya satu kata tersimpan.

Satu-satunya perbedaan dari search: tidak ada pemeriksaan isEndOfWord di akhir. Mencapai akhir prefiks sudah cukup.

Tantangan

Mudah

Tambahkan method startsWith ke class Trie.

Method ini menerima string prefix dan mengembalikan:

true jika ada kata yang disisipkan yang diawali dengan prefix (prefix dapat cocok dengan kata lengkap atau menjadi bagian awal dari kata yang lebih panjang).
false jika tidak.

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"); }
    }
    return 0;
}

Semua pelajaran di Trie: Struktur Data Seri #8

1Pengenalan

Pengenalan Apa Itu Trie?

2Proyek Trie

class TrieNode class Trie Sisipkan CariDiawali DenganHapus Jumlah Kata

3Tantangan Latihan

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

Latihan sendiri: Compiler C online