Operaciones de un árbol de prefijos
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
Comparar un prefijo con cada palabra guardada cuesta tiempo por cada palabra. Las palabras que empiezan igual deberían compartir el trabajo de guardar ese comienzo.
Guarda las palabras como caminos de hijos anidados, un carácter por paso, para que las palabras con un prefijo común compartan los mismos primeros nodos. Que exista un camino no es lo mismo que una palabra termine ahí, así que el final de una palabra necesita su propia marca.
Para insertar, recorre desde la raíz creando cada hijo que falte y luego pon una marca de fin en el último nodo. En ambas consultas recorre igual e informa un fallo en cuanto un carácter no tenga hijo. Una consulta de prefijo tiene éxito si el recorrido termina; una consulta de palabra además necesita la marca de fin en el nodo final.
- Tiempo objetivo
- O(L)
- Espacio objetivo
- O(total characters)
Restricciones
- words are lowercase
- prefixes are non-empty
Solución
Cada nodo es un diccionario que va de un carácter al nodo hijo, así que una palabra es un camino desde la raíz y los prefijos compartidos comparten nodos. Una clave centinela marca los nodos donde realmente termina una palabra guardada, y eso es lo que separa un “app” guardado de un simple prefijo de “apple”. Ambas consultas (queries) usan el mismo recorrido y solo difieren en si exigen el centinela al final. Cada operación toca un nodo por carácter, así que cada una cuesta O(L) para un argumento de longitud L, y el árbol usa O(total de caracteres guardados) de espacio.
class PrefixTree:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for ch in word:
node = node.setdefault(ch, {}) # shared prefixes share nodes
node["$"] = True # a whole word ends here
def _walk(self, s): # the node s leads to, or None
node = self.root
for ch in s:
if ch not in node:
return None
node = node[ch]
return node
def has_word(self, word):
node = self._walk(word)
return node is not None and "$" in node
def has_prefix(self, prefix):
return self._walk(prefix) is not None
t = PrefixTree(); t.insert("apple")
print(t.has_word("apple"), t.has_word("app"), t.has_prefix("app")) # -> True False True
t.insert("app"); e = PrefixTree()
print(t.has_word("app"), e.has_word("app"), e.has_prefix("a")) # -> True False False¿Lo que te frena es la idea y no el código? Fundamentos de tries lo explica.