Saltar al contenido

Operaciones de un árbol de prefijos

Fácil#trie#design~20 min

La misión

Problema

Construye un árbol de prefijos para palabras en minúsculas con tres operaciones. insert(word) guarda una palabra. has_word(word) indica si se guardó exactamente esa palabra. has_prefix(prefix) indica si alguna palabra guardada empieza con el prefijo dado, que no está vacío. Cada operación debe costar un tiempo proporcional a la longitud de su argumento, sin importar cuántas palabras haya guardadas.

Ejemplos

Input:  insert("apple"), has_word("apple"), has_word("app"), has_prefix("app")
Output: True, False, True
Por qué: "app" es el comienzo de una palabra guardada, pero ella misma nunca se guardó
Input:  insert("apple"), insert("app"), has_word("app")
Output: True
Input:  (nothing inserted), has_word("app"), has_prefix("a")
Output: False, False
Por qué: caso límite: un árbol vacío no contiene palabras ni prefijos

Pistas

0 / 3

Tiempo objetivo
O(L)
Espacio objetivo
O(total characters)

Restricciones

  • words are lowercase
  • prefixes are non-empty

¿Lo que te frena es la idea y no el código? Fundamentos de tries lo explica.

Python 3Ctrl+Enter ejecuta