Autocompletado por prefijo sobre un diccionario de palabras. ¿Cuál es la mejor estructura?
Opciones
- Un hash set con todas las palabras
- Un trie (árbol de prefijos) (Opción correcta)
- Un min-heap ordenado por longitud de palabra
- Una linked list de las palabras en orden
Respuesta
Trie (árbol de prefijos)
Por qué
Un trie es un árbol donde cada arista es una letra. Las palabras con el mismo inicio comparten camino: 'car', 'cart' y 'care' pasan por c → a → r.
Para autocompletar 'ca', baja 2 pasos y reúne todas las palabras bajo ese nodo.
El tiempo de búsqueda depende de la longitud del prefijo, no de cuántas palabras haya guardadas.
Recuerda
Búsqueda por prefijo → trie.