Difícil 2 resueltos 66.7% de aceptación

Word Break

Decide whether text can be split into dictionary words.

Lo que aprenderás

  • Marcar qué prefijos se pueden dividir
  • Usar un conjunto para consultas rápidas al diccionario
  • Construir una DP booleana sobre posiciones

Problema

Decide whether text can be split into a sequence of words from words. Words may be reused. Dynamic programming over prefixes solves it efficiently.

Implement can_break(text, words).

Input

text: Lowercase letters only. words: The dictionary; each word has 1–50 lowercase letters.

Output

Return true if a split exists.

Restricciones

0 ≤ length of text ≤ 5,000; 1 ≤ words ≤ 1,000

Ejemplos

Ejemplo 1
Entrada:
text = "applepenapple"
words = ["apple", "pen"]

Salida esperada:
expected = True
Entrada:
std::string text = "applepenapple";
std::vector<std::string> words = {"apple", "pen"};

Salida esperada:
bool expected = true;
Entrada:
string text = "applepenapple";
string[] words = new string[] {"apple", "pen"};

Salida esperada:
bool expected = true;

Explicación

"apple" + "pen" + "apple", reusing "apple".

Ejemplo 2
Entrada:
text = "catsandog"
words = ["cats", "dog", "sand", "and", "cat"]

Salida esperada:
expected = False
Entrada:
std::string text = "catsandog";
std::vector<std::string> words = {"cats", "dog", "sand", "and", "cat"};

Salida esperada:
bool expected = false;
Entrada:
string text = "catsandog";
string[] words = new string[] {"cats", "dog", "sand", "and", "cat"};

Salida esperada:
bool expected = false;

Explicación

Every split leaves "og" or "ando" unmatched: false.

Cómo abordarlo

Inténtalo primero por tu cuenta y luego abre las pistas una a una.

Pista 1

Un prefijo se puede partir si algún punto de corte anterior lo alcanza con una palabra del diccionario.

Pista 2

La programación dinámica sobre posiciones funciona bien si pruebas longitudes de palabra o coincidencias del diccionario de forma eficiente.

Pista 3

El texto vacío se puede partir de forma trivial, pero se debe permitir reutilizar palabras repetidamente durante todo el recorrido.

Complejidad esperada

tiempo O(n^2), espacio extra O(n)

Referencias

Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

# Programador Lenguaje Tiempo Memoria Revisión de IA Solución
1 ННикита Python 806 ms - 5/5 Ver código
2 KKKaneki Ken Python 851 ms - 2/5 Ver código

Aprende de otros

Soluciones de la comunidad

Alerta de spoiler: 2 soluciones completas abajo Intenta resolverlo tú mismo primero. Igual puedes ver el código de otros desarrolladores y las reseñas de IA. Inicia sesión y resuelve el reto para unirte a la discusión.