Implement Trie (Prefix Tree)

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

Un conjunto hash encuentra palabras completas en O(L) , pero no puede responder a una pregunta sobre prefijos sin recorrer todas las palabras. Almacenar cada prefijo en un segundo conjunto cuesta 210 letras para una sola palabra de 20 letras. Un trie almacena cada prefijo compartido una sola vez y responde ambas preguntas con un único recorrido.

MedioTrie

+10

Construye un trie (árbol de prefijos) para palabras en minúsculas con tres operaciones: insert w agrega la palabra w, search w indica si se insertó w como palabra completa y startsWith p indica si alguna palabra insertada comienza con p. Una palabra cuenta como prefijo de sí misma.

La operación i es ops[i] sobre words[i]. Ejecútalas en orden sobre un trie vacío y devuelve una cadena por cada una: "null" para una inserción, "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: car comienza con card, así que startsWith car es "true", pero car nunca se insertó, así que la primera búsqueda es "false". Después de insert 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 comienzan con te, pero ninguna es exactamente te, así que startsWith es "true" y la búsqueda es "false". Ninguna palabra comienza con tex, y tea es un prefijo de sí misma.

Entrada: ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
Salida: ["false", "false", "null", "true", "false", "true"]
Explicación: En el trie vacío, ambas consultas son "false". Después de insert dog, la búsqueda lo encuentra, ninguna palabra comienza con dogs y do es el comienzo de dog.

Para ir más allá

¿Cómo agregarías una operación countPrefix p que devuelva cuántas palabras distintas almacenadas empiezan por p, todavía en tiempo O(L)?

Pistas

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

0 de 3 abiertas

Solución

Un conjunto hash resuelve la consulta search, pero no tiene noción de comienzos, así que startsWith recorrería todas las palabras. Un trie almacena cada palabra como un camino de letras desde la raíz: las palabras que comienzan igual comparten un camino, y una marca indica dónde termina una palabra almacenada. Ambas consultas se convierten en un único recorrido de como máximo L enlaces.

Mantén una lista de palabras y recórrela

Intuición

Mantén cada palabra insertada en una lista. search w compara w con cada palabra almacenada, y startsWith p comprueba si alguna palabra almacenada comienza con p. Es correcto porque comprueba directamente la definición. Con n palabras almacenadas, cada consulta cuesta hasta n comparaciones de hasta L letras: 1.000 palabras y 1.000 consultas hacen un millón de comparaciones de cadenas.

Algoritmo

Empieza con una lista vacía.
insert w: añade w.
search w: devuelve si alguna palabra almacenada es igual a w.
startsWith p: devuelve si alguna palabra almacenada empieza por p.

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 nodos hijos y un indicador de fin

Intuición

Cada nodo representa un prefijo: las letras del camino desde la raíz hasta él. Contiene un enlace a un hijo por cada letra que puede venir a continuación (26 posiciones o un mapa) y una marca isEnd que indica si una palabra almacenada termina exactamente ahí. Insertar tea crea los nodos para t, te y tea; insertar ten después solo añade ten, porque las dos palabras comparten el camino de te.

Un recorrido que encuentra un enlace inexistente demuestra que ninguna palabra almacenada empieza con esas letras: tex se detiene en te, que no tiene un enlace x. Un recorrido que llega al final queda en el nodo de la consulta, así que startsWith es true y search responde con la marca. El nodo de te existe, pero su marca está desactivada, así que search te es false. Cada operación sigue como máximo L enlaces, independientemente de cuántas palabras estén almacenadas, y el trie contiene un nodo por cada prefijo distinto.

Algoritmo

Crea una raíz sin enlaces secundarios y con isEnd desactivado.
insert w: desde la raíz, sigue el enlace de cada letra y crea el nodo cuando no exista. Activa isEnd en el último nodo.
find(p): desde la raíz, sigue el enlace de cada letra; no devuelvas nada en cuanto falte uno; de lo contrario, devuelve el nodo alcanzado.
search w: verdadero cuando find(w) devuelve un nodo con isEnd activado.
startsWith p: verdadero cuando find(p) devuelve un nodo.

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

Hacer que search responda true siempre que exista la ruta. Después de insert card, existe la ruta para car, pero search car debe ser false.
Establecer isEnd solo en los nodos recién creados. Insertar card después de cards no crea nada, pero el último nodo necesita su indicador.
Crear un hijo nuevo cuando el enlace ya existe. Insertar ten con un nodo t nuevo hace que se pierda tea.
Leer más allá del final de la ruta. startsWith sunny con solo sun almacenado debe detenerse en el primer enlace faltante y responder false.

Preguntas frecuentes3

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

Insertar, buscar y StartsWith siguen un enlace por letra, así que cada operación tarda O(L) para una palabra de longitud L, independientemente de cuántas palabras estén almacenadas. El espacio es de O(T) nodos para un total de T letras insertadas, y cada nodo contiene hasta 26 enlaces secundarios.

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

Un conjunto hash encuentra palabras completas en O(L), pero no puede responder a una pregunta sobre prefijos sin recorrer todas las palabras. Almacenar cada prefijo en un segundo conjunto cuesta 210 letras para una sola palabra de 20 letras. Un trie almacena cada prefijo compartido una sola vez y responde ambas preguntas con un único recorrido.

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

Un arreglo encuentra un hijo con un índice, pero cuesta 26 espacios por nodo, incluso para un nodo con un solo hijo. Un mapa almacena solo los hijos que existen y funciona con cualquier alfabeto, a cambio de un hash por letra. Para el inglés en minúsculas, cualquiera de las dos opciones funciona; para Unicode o los tries dispersos, un mapa ahorra memoria.

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

Prueba #1

Prueba #2

Prueba #3

Argumentos

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

Salida Esperada

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