Saltar al contenido

Palabras del diccionario en un texto

Fácil#trie#prefix-pruning~15 min

La misión

Problema

Dado un string (cadena) text y una lista de words distintas, devuelve cada par [i, j] tal que el slice de text del índice i al j, ambos incluidos, sea una de las palabras. Las apariciones pueden superponerse. Devuelve los pares ordenados por i y luego por j.

Ejemplos

Input:  text = "bytesofcode", words = ["byte", "bytes", "code", "of", "so"]
Output: [[0, 3], [0, 4], [4, 5], [5, 6], [7, 10]]
Por qué: byte, bytes, so, of y code, donde so y of comparten la letra o
Input:  text = "ababa", words = ["aba", "ab"]
Output: [[0, 1], [0, 2], [2, 3], [2, 4]]
Input:  text = "abc", words = ["d"]
Output: []
Por qué: caso límite: no aparece ninguna palabra

Pistas

0 / 3

Tiempo objetivo
O(n · L + W)
Espacio objetivo
O(W + n · L)

Restricciones

  • the words are distinct

¿Lo que te frena es la idea y no el código? Búsqueda de palabras con un trie lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio