Commence par
Leçon 7 sur 14 du cours Tries - Série Structures de données n°8 de Coddy.
La raison d'être des tries est de répondre rapidement aux questions sur les préfixes. startsWith vérifie si n'importe quel mot stocké commence par un préfixe donné - il ne se soucie pas de savoir si ce préfixe lui-même est un mot complet inséré.
Le parcours est presque identique à search : à partir de la racine, suivez les enfants un caractère à la fois. Si un caractère manque en chemin, aucun mot stocké ne commence par ce préfixe, donc retournez false. Si vous parcourez chaque caractère sans vous arrêter, la réponse est true - le sous-arbre sous ce nœud contient au moins un mot stocké.
La seule différence par rapport à search : il n'y a pas de vérification isEndOfWord à la fin. Atteindre la fin du préfixe est suffisant.
Défi
FacileAjoutez une méthode startsWith à la classe Trie.
Elle reçoit une chaîne prefix et renvoie :
truesi un mot inséré commence parprefix(le préfixe peut correspondre à un mot complet, ou être la partie initiale d'un mot plus long).falsesinon.
Essayez vous-même
#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;
}