StartsWith
Coddy'nin Trie - Veri Yapıları Serisi #8 kursunda ders 7 / 14.
Trie yapılarının var olmasının temel nedeni, önek sorularını hızlı bir şekilde yanıtlamaktır. startsWith, saklanan herhangi bir kelimenin verilen bir önekle başlayıp başlamadığını kontrol eder; bu önekin kendisinin tam olarak eklenmiş bir kelime olup olmadığıyla ilgilenmez.
Gezinme işlemi search ile neredeyse aynıdır: kökten başlayarak çocukları her seferinde bir karakter olacak şekilde takip edin. Yol boyunca bir karakter eksikse, saklanan hiçbir kelime bu önekle başlamıyor demektir, bu nedenle false döndürün. Durmadan her karakteri geçerseniz cevap true olur; bu düğümün altındaki alt ağaç en az bir saklanan kelime içerir.
search işleminden tek farkı: sonunda bir isEndOfWord kontrolü olmamasıdır. Önekin sonuna ulaşmak yeterlidir.
Görev
KolayTrie sınıfına bir startsWith metodu ekleyin.
Bu metot bir prefix dizesi alır ve şunları döndürür:
- Eğer eklenen bazı kelimeler
prefixile başlıyorsatrue(önek tam bir kelimeyle eşleşebilir veya daha uzun bir kelimenin başlangıç kısmı olabilir). - Aksi takdirde
false.
Kendin dene
#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;
}