Quebra de Palavras
Lição 14 de 14 do curso Tries - Série de Estruturas de Dados #8 da Coddy.
Dada uma string s e um dicionário de palavras, podemos dividir s em uma sequência de palavras do dicionário sem sobrar nada? "leetcode" se divide como "leet" + "code" se ambos estiverem no dicionário; "catsandog" não se divide, não importa como o cortemos.
Uma passagem de programação dinâmica resolve isso. Defina dp[i] como os primeiros i caracteres podem ser segmentados? Comece com dp[0] = true. Para cada i onde dp[i] for true, percorra a trie a partir da posição i na string; toda vez que o percurso aterrissar em um nó isEndOfWord no índice j, defina dp[j+1] = true.
A trie torna cada percurso rápido: um único caractere ausente o encerra. A resposta final reside em dp[n].
Desafio
MédioEscreva uma função wordBreak que recebe uma string s e um array de strings dictionary, e retorna true se s puder ser dividida em um ou mais pedaços sem espaços que estejam todos no dicionário, ou false caso contrário.
Uma string s vazia é sempre divisível.
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 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 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