Autocompletado
Lección 12 de 14 del curso Tries - Serie de Estructuras de Datos #8 de Coddy.
Este es el caso de uso clásico para un trie: dado lo que el usuario ha escrito hasta ahora, listar cada palabra almacenada que comience con ese prefijo. Camina hasta el nodo del prefijo; si no puedes, no devuelvas nada. Luego explora el subárbol de abajo y recolecta cada palabra que encuentres.
A medida que desciendes durante el DFS, construye la palabra de forma incremental añadiendo el carácter de la arista que acabas de cruzar. Cada vez que llegues a un nodo donde isEndOfWord sea true, la ruta actual es una de las coincidencias.
Desafío
IntermedioEscribe una función autocomplete que reciba un arreglo de cadenas words y una cadena prefix, y devuelva la lista de palabras del arreglo que comienzan con prefix.
La lista devuelta debe estar en orden ascendente (alfabético). Si ninguna palabra coincide, devuelve una lista vacía.
Debes utilizar la clase Trie (proporcionada en trie junto con trienode); no utilices elementos integrados del lenguaje como conjuntos, diccionarios o mapas para contar o rastrear.
Pruébalo tú mismo
#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 las lecciones de Tries - Serie de Estructuras de Datos #8
3Desafíos de práctica
Prefijo común más largoContar palabras con prefijoAutocompletadoPalabra más larga en el diccionarioDivisión de palabras