Cari

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

Mencari sebuah kata merupakan kebalikan alami dari penyisipan: telusuri dari akar satu karakter setiap kali, dengan mengikuti child yang cocok. Jika pada titik mana pun node saat ini tidak memiliki child untuk karakter berikutnya, kata tersebut tidak ada di trie dan kita bisa langsung mengembalikan false.

Jika kita berhasil menelusuri setiap karakter, kita akan sampai di sebuah node. Jawabannya adalah nilai flag isEndOfWord pada node tersebut. Inilah perbedaan pentingnya: setelah menyisipkan "car", jalur untuk "ca" ada di trie, tetapi search("ca") tetap harus mengembalikan false karena tidak ada yang menandai node tersebut sebagai akhir sebuah kata.

Tantangan

Mudah

Tambahkan method search ke class Trie.

Method ini menerima string word dan mengembalikan:

true jika word pernah dimasukkan ke dalam trie.
false jika tidak, termasuk saat hanya prefiks word yang ada, atau hanya kata yang lebih panjang dan diawali word yang tersimpan.

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

Semua pelajaran di Trie: Struktur Data Seri #8

1Pengenalan

Pengenalan Apa Itu Trie?

2Proyek Trie

class TrieNode class Trie SisipkanCariDiawali Dengan Hapus Jumlah Kata

3Tantangan Latihan

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

Latihan sendiri: Compiler C online