Implement Trie (Prefix Tree)

+10

Un trie, o árbol de prefijos, almacena palabras para que las consultas sobre sus comienzos sean rápidas. Construye uno para palabras en minúsculas con tres operaciones: insert w agrega la palabra w, search w indica si se insertó la propia palabra w y startsWith p indica si alguna palabra insertada comienza con p. Una palabra cuenta como prefijo de sí misma.

Recibes las operaciones en orden como ops, y words[i] es la palabra o el prefijo correspondiente a ops[i]. Ejecútalas en un mismo trie que comienza vacío y devuelve una cadena por operación: "null" para una inserción y "true" o "false" para una búsqueda o una operación startsWith.

Función

trieOps(ops: string-array, words: string-array) → string-array

opsstring-array: las operaciones, en el orden en que se ejecutan
wordsstring-array: la palabra o el prefijo de cada operación
Devuelvestring-array: una respuesta por operación, como texto

Restricciones

1 ≤ ops.length ≤ 2000
words.length == ops.length
Cada ops[i] es insert, search o startsWith.
1 ≤ words[i].length ≤ 20
words[i] contiene únicamente letras minúsculas del inglés.

Ejemplos

Entrada: ops = ["insert", "search", "startsWith", "insert", "search"]words = ["card", "car", "car", "car", "car"]
Salida: ["null", "false", "true", "null", "true"]
Explicación: Al principio solo se almacena card, por lo que buscar car devuelve "false": nunca se insertó como palabra. Es el comienzo de card, así que startsWith car devuelve "true". Una vez insertado car, la búsqueda lo encuentra.

Entrada: ops = ["insert", "insert", "startsWith", "search", "startsWith", "search", "startsWith"]words = ["tea", "ten", "te", "te", "tex", "ten", "tea"]
Salida: ["null", "null", "true", "false", "false", "true", "true"]
Explicación: Ambas palabras empiezan con te, así que startsWith te es "true", pero ninguna palabra es exactamente te, así que la búsqueda falla. Ninguna palabra empieza con tex. Se insertó ten, y tea es un prefijo de sí misma, así que las dos últimas respuestas son "true".

Entrada: ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
Salida: ["false", "false", "null", "true", "false", "true"]
Explicación: El trie empieza vacío, así que las dos primeras respuestas son "false". Después de insertar dog, la búsqueda lo encuentra, ninguna palabra empieza con dogs y do es el comienzo de dog.

+16 pruebas ocultas al enviar

Para ir más allá

¿Cómo agregarías una operación countPrefix p que devuelva cuántas palabras distintas almacenadas empiezan con p, manteniendo un tiempo de ejecución de O(L)?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Un conjunto hash responde a search de inmediato, pero startsWith pregunta por todas las palabras que comienzan de cierta manera, y un conjunto no tiene noción de comienzos. Un trie almacena los propios comienzos: cada palabra es un recorrido de letras desde la raíz, las palabras que comienzan igual comparten el inicio de su recorrido, y una marca en un nodo indica dónde termina una palabra almacenada. Ambas preguntas requieren entonces recorrer como máximo L enlaces, donde L es la longitud de la consulta, independientemente de cuántas palabras estén almacenadas.

Conserva una lista de palabras y recórrela

Intuición

Mantén cada palabra insertada en una lista. Para search w, compara w con cada palabra almacenada. Para startsWith p, comprueba si alguna palabra almacenada empieza por p. En el segundo ejemplo, startsWith te examina primero tea y se detiene ahí; startsWith tex tiene que examinar ambas palabras antes de responder "false".

Esto es correcto y, con los límites de aquí, termina, pero cada consulta tiene que recorrer todas las palabras almacenadas. Si hay n palabras almacenadas, una consulta cuesta hasta n comparaciones de hasta L letras cada una. 1,000 palabras almacenadas y 1,000 consultas implican un millón de comparaciones de cadenas, y el trabajo sigue creciendo con el diccionario. Tampoco se comparte nada: tea y ten almacenan cada una su propia t y e.

Algoritmo

Empieza con una lista vacía de palabras.
Para insert w: añade w a la lista.
Para search w: devuelve si alguna palabra almacenada es igual a w.
Para startsWith p: devuelve si alguna palabra almacenada empieza con p.
Registra cada respuesta como texto y devuelve la lista.

def trieOps(ops, words):
    stored = []
    result = []
    for op, word in zip(ops, words):
        if op == "insert":
            stored.append(word)
            result.append("null")
        elif op == "search":
            found = any(s == word for s in stored)
            result.append("true" if found else "false")
        else:
            found = any(s.startswith(word) for s in stored)
            result.append("true" if found else "false")
    return result

Un trie: enlaces a los hijos y una marca de fin

Intuición

Cada nodo de un trie representa un prefijo: las letras del camino desde la raíz hasta él. La raíz representa el prefijo vacío. Un nodo contiene dos cosas: un enlace secundario por cada letra que puede venir a continuación (un arreglo de 26 posiciones o un mapa de letras a nodos) y una marca, isEnd, que indica si una palabra almacenada termina exactamente en este nodo.

insert recorre la palabra desde la raíz. Para cada letra, sigue el enlace secundario y, si falta el enlace, primero crea el nodo; en la última letra, establece isEnd. En el segundo ejemplo, insertar tea crea los nodos para t, te y tea, y marca tea. Insertar ten reutiliza t y te, y añade solo ten. Las dos palabras comparten el camino para te, de ahí el nombre árbol de prefijos.

search y startsWith realizan el mismo recorrido sin crear nada. Si falta un enlace, ninguna palabra almacenada comienza con esas letras, así que ambas responden false: tex se detiene en el nodo para te, que no tiene un enlace x. Si el recorrido llega al final, el nodo en el que se encuentra es el prefijo por el que preguntaste. startsWith responde true, y search responde según la marca de ese nodo. El nodo para te existe, pero su marca está desactivada, porque las palabras que pasan por él terminan más abajo. Así que startsWith te es true y search te es false.

La marca es lo que distingue una palabra de un prefijo. En el primer ejemplo, después de insertar card, existe el camino c, a, r. Sin la marca, search car respondería true por error. Insertar car más adelante no crea ningún nodo; solo activa la marca.

Cada operación sigue como máximo L enlaces, donde L es la longitud de su palabra, así que cuesta O(L), sin importar cuántas palabras estén almacenadas. El trie contiene un nodo por cada prefijo distinto, nunca más que el número total de letras insertadas.

Algoritmo

Define un nodo con enlaces a sus hijos (26 posiciones o un mapa) y una marca isEnd, y crea una raíz vacía.
Para insert w: desde la raíz, sigue el enlace correspondiente a cada letra de w, creando el nodo cuando falte el enlace. Establece isEnd en el último nodo.
Escribe una función auxiliar find(p): desde la raíz, sigue el enlace correspondiente a cada letra de p y detente en cuanto falte uno. Devuelve el nodo alcanzado.
Para search w: responde verdadero cuando find(w) llegue a un nodo cuya marca isEnd esté establecida.
Para startsWith p: responde verdadero cuando find(p) llegue a un nodo.
Ejecuta las operaciones en orden y registra "null", "true" o "false" para cada una.

class TrieNode:
    def __init__(self):
        self.children = {}   # letter -> TrieNode
        self.is_end = False  # does a stored word end at this node?


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def _find(self, prefix):
        # Follow the letters from the root; None as soon as a link is missing.
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._find(prefix) is not None


def trieOps(ops, words):
    trie = Trie()
    result = []
    for op, word in zip(ops, words):
        if op == "insert":
            trie.insert(word)
            result.append("null")
        elif op == "search":
            result.append("true" if trie.search(word) else "false")
        else:
            result.append("true" if trie.starts_with(word) else "false")
    return result

Errores comunes y casos límite

La mayoría de los errores se deben a confundir «aquí termina una palabra» con «aquí pasa una palabra».

Hacer que search responda true siempre que exista la ruta. Después de insertar card, existe la ruta para car, pero car nunca se insertó.
Establecer isEnd solo en los nodos recién creados. Insertar card después de cards no crea nada, pero el último nodo sigue necesitando su marca.
Crear un hijo nuevo incluso cuando ya existe el enlace. Eso desconecta todo lo que está almacenado debajo: insertar ten con un nodo t nuevo hace que se pierda tea.
Olvidar que una palabra es prefijo de sí misma. Después de insertar tea, startsWith tea es true.
Seguir leyendo más allá del final de la ruta. Un prefijo más largo que todas las palabras, como sunny cuando solo está almacenado sun, debe detenerse en el primer enlace que falte y responder false.
Devolver valores booleanos o dejar las inserciones fuera de la respuesta. Cada operación obtiene una cadena, incluida "null" para una inserción.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de un trie?

Insert, search y startsWith siguen un enlace por cada letra de su argumento, por lo que cada uno tarda O(L) para una palabra de longitud L, independientemente de cuántas palabras estén almacenadas. El trie contiene como máximo un nodo por cada letra insertada, así que el espacio es de O(T) nodos para un total de T letras insertadas, y cada nodo almacena hasta 26 enlaces secundarios.

¿Por qué usar un trie en lugar de un conjunto hash?

Un conjunto hash responde a consultas de palabras completas en O(L), pero no puede responder a una consulta de prefijo sin recorrer todas las palabras. Podrías añadir un segundo conjunto que contenga todos los prefijos de cada palabra, pero entonces una palabra de 20 letras almacena 20 prefijos con 210 letras entre ellos. Un trie almacena cada prefijo compartido una sola vez y responde a ambas preguntas con el mismo recorrido. Con 26 posiciones de matriz por nodo, un recorrido bajo un prefijo también encuentra las palabras en orden alfabético, lo que necesita el autocompletado.

¿Debería un nodo del trie usar un arreglo de 26 enlaces o un mapa hash?

Un arreglo ofrece la búsqueda más rápida de hijos, un índice por letra, pero cada nodo ocupa 26 espacios incluso cuando usa solo uno. Un mapa almacena solo los hijos que existen y funciona con cualquier alfabeto, a cambio de un paso de hash por letra. Para palabras en inglés en minúsculas, cualquiera de las dos opciones es adecuada; para texto Unicode o tries dispersos, un mapa ahorra mucha memoria.

¿Dónde se utilizan los tries en la práctica?

El autocompletado y las sugerencias de búsqueda recorren un trie hasta llegar al prefijo escrito y enumeran las palabras que hay debajo. Los correctores ortográficos, los juegos de palabras que buscan palabras del diccionario en un tablero y los enrutadores que encuentran el prefijo de dirección coincidente más largo usan la misma estructura. Siempre que muchas cadenas compartan el comienzo y hagas consultas por comienzo, un trie es adecuado.

Python

def trieOps(ops, words):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

ops = ["insert", "search", "startsWith", "insert", "search"]
words = ["card", "car", "car", "car", "car"]

Esperado

["null", "false", "true", "null", "true"]