Contar Palavras com Prefixo
Lição 11 de 14 do curso Tries - Série de Estruturas de Dados #8 da Coddy.
Quantas palavras armazenadas começam com um determinado prefixo? Após inserir cada palavra, percorra a partir da raiz um caractere por vez ao longo do prefixo. Se algum caractere estiver faltando, a resposta é zero - nenhuma palavra poderia começar com esse prefixo.
Se você chegar ao fim do prefixo, você pousará em um nó. Cada palavra armazenada que começa com este prefixo vive em algum lugar na subárvore enraizada ali. Conte-as percorrendo a subárvore e adicionando 1 para cada nó onde isEndOfWord é true.
Desafio
FácilEscreva uma função countWordsWithPrefix que recebe um array de strings words e uma string prefix, e retorna o número de palavras no array que começam com o prefixo fornecido.
Um prefixo vazio corresponde a todas as palavras.
Você deve usar a classe Trie (fornecida em trie junto com trienode) - não use recursos nativos da linguagem como sets, dicts ou maps para contar/rastrear.
Experimente você mesmo
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char l1[4096], prefix[1024];
if (!fgets(l1, sizeof(l1), stdin)) l1[0] = 0;
if (!fgets(prefix, sizeof(prefix), stdin)) prefix[0] = 0;
l1[strcspn(l1, "\r\n")] = '\0';
prefix[strcspn(prefix, "\r\n")] = '\0';
char* words[1024]; int n = 0;
char* tok = strtok(l1, " \t");
while (tok && n < 1024) { words[n++] = tok; tok = strtok(NULL, " \t"); }
printf("%d\n", countWordsWithPrefix(words, n, prefix));
return 0;
}
Todas as lições de Tries - Série de Estruturas de Dados #8
3Desafios Práticos
Prefixo Comum Mais LongoContar Palavras com PrefixoAutocompletarMaior Palavra no DicionárioQuebra de Palavras