Búsqueda por prefijo
Paso 1 de 9
Hay tres palabras guardadas. El usuario aún no escribió nada, así que todas siguen siendo candidatas.
La idea
El autocompletado hace una pregunta distinta de “¿esto es una palabra?”. Pregunta “¿qué empieza con esto?”.
Recorre el prefijo una vez: cuesta un salto por cada carácter escrito. El nodo donde caes es la raíz de un subárbol que guarda exactamente las palabras con ese prefijo, así que reunir las sugerencias nunca toca el resto del diccionario.
Ejemplo del mundo real
El teclado de un celular que sugiere palabras después de tres letras. No puede volver a recorrer 200 000 palabras entre una tecla y otra, así que guarda la posición a la que llegó con “cat” y, en la siguiente tecla, da un salto más en lugar de empezar de cero.
El código
Te toca
Completa el espacio en blanco.
trie = {"a": {"t": {"$": 1}}}
node = trie
for ch in "ax":
node = node.get(ch)
if node ___ None:
break
print(node) # NoneMini quiz
1 / 3