Palabras del diccionario en un texto
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
Comparar cada slice del texto con un conjunto de palabras funciona, pero construye O(n²) slices, y la mayoría no es el comienzo de ninguna palabra.
Desde un índice de inicio fijo, un árbol de prefijos te permite extender el slice una letra a la vez y detenerte en el momento en que ninguna palabra continúa con esa letra.
Inserta cada palabra en un trie con una marca de fin. Para cada inicio i, recorre el trie siguiendo text[i], text[i + 1] y así sucesivamente, anota [i, j] cada vez que el nodo marque el fin de una palabra, y detente cuando la siguiente letra no tenga hijo.
- Tiempo objetivo
- O(n · L + W)
- Espacio objetivo
- O(W + n · L)
Restricciones
- the words are distinct
Solución
El trie (árbol de prefijos) convierte cada posición de inicio en un recorrido que se detiene en cuanto el texto se aparta de todas las palabras, la misma poda que acelera una búsqueda en cuadrícula guiada por un trie: un conjunto de palabras solo responde si un slice completo es una palabra, mientras que un trie también responde si todavía puede llegar a serlo. Recorrer desde el inicio i con j creciente informa las coincidencias de ese inicio en orden, y los inicios se visitan en orden, así que la salida no necesita ordenarse. Para un texto de longitud n y una palabra más larga de longitud L, el tiempo es O(n · L) más O(W) para construir el trie con W letras en total, y el espacio es O(W).
def word_positions(text, words):
root = {}
for w in words:
node = root
for ch in w:
node = node.setdefault(ch, {})
node["$"] = True # a word ends here
found = []
for i in range(len(text)):
node = root
for j in range(i, len(text)):
node = node.get(text[j])
if node is None: # no word continues this way
break
if "$" in node:
found.append([i, j])
return found
print(word_positions("bytesofcode", ["byte", "bytes", "code", "of", "so"])) # -> [[0, 3], [0, 4], [4, 5], [5, 6], [7, 10]]
print(word_positions("ababa", ["aba", "ab"])) # -> [[0, 1], [0, 2], [2, 3], [2, 4]]
print(word_positions("abc", ["d"])) # -> []¿Lo que te frena es la idea y no el código? Búsqueda de palabras con un trie lo explica.