Búsqueda por prefijo y Starts-With

La principal ventaja del Trie frente a una tabla hash son las eficientes consultas de prefijos. Una consulta de prefijo responde a preguntas como: «¿cuántas palabras almacenadas comienzan con este prefijo?», «¿cuáles son todas las palabras almacenadas con este prefijo?» o, sencillamente, «¿existe alguna palabra con este prefijo?». Estas consultas son O(p), donde p es la longitud del prefijo, independientemente del número total de palabras almacenadas, lo que hace que los Tries sean ideales para el autocompletado y las sugerencias de búsqueda.

starts_with(prefix) devuelve True si alguna palabra almacenada comienza con el prefijo indicado. Recorra el Trie siguiendo cada carácter del prefijo. Si se pueden seguir todos los caracteres sin que falte ninguna arista, el prefijo existe y al menos una palabra comienza con él. La implementación es idéntica a search, salvo que devuelve True en cuanto termina el recorrido: no comprueba is_end.

Para implementar el autocompletado, recorra el Trie hasta el nodo final del prefijo y, después, realice un DFS (o BFS) desde ese nodo para recopilar todas las palabras que parten de él. Ante­ponga el prefijo a cada sufijo recopilado para reconstruir las palabras completas. Es una operación O(p + W), donde W es el número total de caracteres de todas las palabras coincidentes.

Para obtener un autocompletado ordenado, recorra los hijos en orden alfabético durante el DFS (itere sobre sorted(node.children.items())). Como los hijos se almacenan en un diccionario, esto añade una sobrecarga de O(ALPHABET_SIZE × depth), pero garantiza resultados ordenados lexicográficamente. Un Trie basado en arreglos siempre recorre los hijos en orden alfabético, ya que los índices del 0 al 25 están ordenados.

Para obtener las k mejores sugerencias por frecuencia, añada a cada nodo un contador del número de veces que se ha buscado la palabra que termina en él. Al recopilar las sugerencias, utilice un montículo máximo de tamaño k. Esto reduce a O(k) el conjunto de resultados del DFS, que sería de O(W), sin materializar todas las coincidencias. Los motores de búsqueda reales combinan el recorrido de prefijos del Trie con datos de frecuencia para ofrecer sugerencias rápidas y relevantes.

LeetCode 208, «Implement Trie (Prefix Tree)», solicita exactamente: insert(word), search(word), que devuelve un booleano de coincidencia exacta, y startsWith(prefix), que devuelve un booleano de coincidencia de prefijo. Esta es la implementación canónica de un Trie. Recuerde: search requiere is_end=True; startsWith solo requiere que exista la ruta del prefijo.

Una alternativa elegante consiste en almacenar el Trie como diccionarios anidados con una clave especial centinela, como '#', para marcar los finales de las palabras, eliminando la necesidad de una clase TrieNode. Es una opción compacta y adecuada para entrevistas, aunque ligeramente menos legible que los objetos TrieNode explícitos. Ambas implementaciones son válidas; la versión con diccionario se escribe más rápido cuando hay presión de tiempo.

Para encontrar el prefijo común más largo de una lista de cadenas, inserte todas las cadenas en el Trie y recorra desde la raíz siguiendo la única ruta existente mientras se cumplan estas condiciones: (1) el nodo actual tiene exactamente un hijo y (2) is_end es False. Deténgase cuando deje de cumplirse cualquiera de las condiciones. La ruta seguida es el prefijo común más largo.

Replace Words (LeetCode 648): dado un diccionario de palabras raíz y una oración, reemplace cada palabra de la oración por la raíz coincidente más corta del diccionario. Inserte todas las raíces en un Trie. Para cada palabra de la oración, recorra el Trie hasta encontrar el final de una raíz y devuelva esa raíz como reemplazo. Si no coincide ninguna raíz, conserve la palabra original. Esto se ejecuta en O(total chars), frente a O(n × m) mediante fuerza bruta.

Map Sum (LeetCode 677): inserte pares clave-valor y devuelva la suma de todos los valores cuyas claves tienen un prefijo determinado. Añada a cada TrieNode un campo val. Para insert, recorra el Trie hasta el final y establezca el valor; para las consultas de suma, recorra el Trie hasta el nodo final del prefijo y calcule mediante DFS la suma de todos los campos val que hay debajo. Como alternativa, almacene la suma acumulada en cada nodo durante la inserción para realizar consultas en O(p).

En los sistemas de autocompletado en producción, devolver todas las palabras con un prefijo no es práctico cuando coinciden miles de palabras. En su lugar, use un max-heap de tamaño k durante el recorrido DFS: mantenga las k palabras con mayor puntuación encontradas hasta el momento. Detenga pronto las ramas del DFS si no pueden contener una palabra del top-k (poda mediante una cota superior de puntuación). De este modo se obtiene O(p + k × log k) por consulta para k sugerencias, mucho mejor que recopilar todas las coincidencias.

Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

En esta lección aprendió: starts_with recorre la ruta del prefijo y devuelve True si existe; no es necesario comprobar is_end, el DFS de autocomplete recopila todas las palabras desde el nodo final del prefijo añadiendo caracteres a medida que desciende, y ampliar los nodos con recuentos o valores permite realizar consultas de suma y obtener sugerencias top-k. A continuación añadiremos la búsqueda con comodines y expresiones regulares al trie.