Autocompletar
Lição 12 de 14 do curso Tries - Série de Estruturas de Dados #8 da Coddy.
Este é o caso de uso clássico para uma trie: dado o que o usuário digitou até agora, liste todas as palavras armazenadas que começam com esse prefixo. Caminhe até o nó do prefixo; se não conseguir, não retorne nada. Em seguida, explore a subárvore abaixo e colete todas as palavras que encontrar.
À medida que você desce durante a DFS, construa a palavra incrementalmente anexando o caractere da aresta que você acabou de atravessar. Cada vez que você atingir um nó onde isEndOfWord for true, o caminho atual será uma das correspondências.
Desafio
MédioEscreva uma função autocomplete que recebe um array de strings words e uma string prefix, e retorna a lista de palavras do array que começam com prefix.
A lista retornada deve estar em ordem crescente (alfabética). Se nenhuma palavra corresponder, retorne uma lista vazia.
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"); }
int out_n = 0;
char** res = autocomplete(words, n, prefix, &out_n);
for (int i = 0; i < out_n; i++) { printf("%s", res[i]); if (i + 1 < out_n) printf(" "); }
printf("\n");
if (res) free(res);
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