División de palabras
Lección 14 de 14 del curso Tries - Serie de Estructuras de Datos #8 de Coddy.
Dada una cadena s y un diccionario de palabras, ¿podemos dividir s en una secuencia de palabras del diccionario sin que sobre nada? "leetcode" se divide como "leet" + "code" si ambas están en el diccionario; "catsandog" no se divide sin importar cómo la cortemos.
Una pasada de programación dinámica lo resuelve. Define dp[i] como ¿pueden segmentarse los primeros i caracteres? Comienza con dp[0] = true. Para cada i donde dp[i] sea true, recorre el trie desde la posición i en la cadena; cada vez que el recorrido aterrice en un nodo isEndOfWord en el índice j, establece dp[j+1] = true.
El trie hace que cada recorrido sea rápido: un solo carácter faltante lo termina. La respuesta final reside en dp[n].
Desafío
IntermedioEscribe una función wordBreak que reciba una cadena s y un arreglo de cadenas dictionary, y devuelva true si s puede dividirse en una o más piezas sin espacios en blanco que estén todas en el diccionario, o false en caso contrario.
Una cadena s vacía siempre se puede dividir.
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 s[4096], dLine[4096];
if (!fgets(s, sizeof(s), stdin)) s[0] = 0;
if (!fgets(dLine, sizeof(dLine), stdin)) dLine[0] = 0;
s[strcspn(s, "\r\n")] = '\0';
dLine[strcspn(dLine, "\r\n")] = '\0';
char* d[1024]; int dn = 0;
char* tok = strtok(dLine, " \t");
while (tok && dn < 1024) { d[dn++] = tok; tok = strtok(NULL, " \t"); }
printf("%s\n", wordBreak(s, d, dn) ? "true" : "false");
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