Começa com
Lição 7 de 14 do curso Tries - Série de Estruturas de Dados #8 da Coddy.
A razão principal pela qual as tries existem é para responder perguntas de prefixo rapidamente. startsWith verifica se qualquer palavra armazenada começa com um determinado prefixo - não importa se esse prefixo em si é uma palavra completa inserida.
O percurso é quase idêntico ao search: a partir da raiz, siga os filhos um caractere por vez. Se um caractere estiver faltando ao longo do caminho, nenhuma palavra armazenada começa com esse prefixo, então retorne false. Se você percorrer todos os caracteres sem parar, a resposta é true - a subárvore abaixo desse nó contém pelo menos uma palavra armazenada.
A única diferença em relação ao search: não há uma verificação isEndOfWord no final. Chegar ao fim do prefixo é o suficiente.
Desafio
FácilAdicione um método startsWith à classe Trie.
Ele recebe uma string prefix e retorna:
truese alguma palavra inserida começar comprefix(o prefixo pode corresponder a uma palavra completa ou ser a parte inicial de uma palavra mais longa).falsecaso contrário.
Experimente você mesmo
#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;
}