Palabra más larga en el diccionario
Lección 13 de 14 del curso Tries - Serie de Estructuras de Datos #8 de Coddy.
Dado un diccionario de palabras, encuentra la palabra más larga que se pueda construir un carácter a la vez añadiendo a una palabra que ya esté en el diccionario. "world" solo cuenta si todas las palabras "w", "wo", "wor" y "worl" también son palabras almacenadas.
Este es un caso perfecto para un trie. Inserta cada palabra, luego realiza una DFS desde la raíz, pero solo desciende a un hijo si está marcado como isEndOfWord. De esa manera, cada nodo que visitemos durante la DFS representa un camino donde cada prefijo es en sí mismo una palabra.
Haz un seguimiento del camino más largo. Si dos caminos tienen la misma longitud, elige el que sea lexicográficamente menor.
Desafío
IntermedioEscribe una función longestWordInDict que reciba un arreglo de cadenas words y devuelva la palabra más larga que pueda construirse añadiendo un carácter a la vez a una palabra más corta presente en el arreglo.
Si dos palabras empatan en longitud, devuelve la que sea lexicográficamente menor. Si el arreglo está vacío, devuelve una cadena vacía.
Debes utilizar 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 line[4096];
if (!fgets(line, sizeof(line), stdin)) line[0] = 0;
line[strcspn(line, "\r\n")] = '\0';
char* words[1024]; int n = 0;
char* tok = strtok(line, " \t");
while (tok && n < 1024) { words[n++] = tok; tok = strtok(NULL, " \t"); }
char* res = longestWordInDict(words, n);
printf("%s\n", 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