Contar palabras con prefijo
Lección 11 de 14 del curso Tries - Serie de Estructuras de Datos #8 de Coddy.
¿Cuántas palabras almacenadas comienzan con un prefijo dado? Después de insertar cada palabra, recorra desde la raíz un carácter a la vez a lo largo del prefijo. Si falta algún carácter, la respuesta es cero: ninguna palabra podría comenzar con ese prefijo.
Si llega al final del prefijo, aterrizará en un nodo. Cada palabra almacenada que comienza con este prefijo vive en algún lugar del subárbol con raíz allí. Cuéntelas recorriendo el subárbol y sumando 1 por cada nodo donde isEndOfWord sea true.
Desafío
FácilEscribe una función countWordsWithPrefix que recibe un arreglo de cadenas words y una cadena prefix, y devuelve el número de palabras en el arreglo que comienzan con el prefijo dado.
Un prefijo vacío coincide con cada palabra.
Debes usar la clase Trie (proporcionada en trie junto con trienode); no utilices funciones integradas 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"); }
printf("%d\n", countWordsWithPrefix(words, n, prefix));
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