Buscar
Lección 6 de 14 del curso Tries - Serie de Estructuras de Datos #8 de Coddy.
Buscar una palabra es el opuesto natural de insertar: baja desde la raíz un carácter a la vez, siguiendo a los hijos correspondientes. Si en cualquier punto el nodo actual no tiene un hijo para el siguiente carácter, la palabra no está en el trie y podemos devolver false de inmediato.
Si logramos recorrer cada carácter, aterrizamos en un nodo. La respuesta es lo que diga el indicador isEndOfWord de ese nodo. Esta es la distinción crítica: después de insertar "car", la ruta para "ca" existe en el trie, pero search("ca") aún debe devolver false porque nadie marcó ese nodo como el final de una palabra.
Desafío
FácilAgrega un método search a la clase Trie.
Este recibe una cadena word y devuelve:
truesiwordfue insertada en el trie anteriormente.falseen caso contrario (incluyendo cuando solo existe un prefijo deword, o cuando solo se almacena una palabra más larga que comienza conword).
Pruébalo tú mismo
#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;
}