Busca por prefixo
Passo 1 de 9
Há três palavras guardadas. O usuário ainda não digitou nada, então todas ainda são candidatas.
A ideia
O autocomplete faz uma pergunta diferente de “isto é uma palavra?”. Ele pergunta “o que começa com isto?”.
Percorra o prefixo uma vez — isso custa um salto por caractere digitado. O nó em que você para é a raiz de uma subárvore com exatamente as palavras que têm esse prefixo, então juntar as sugestões nunca toca o resto do dicionário.
Exemplo do mundo real
O teclado do celular sugere palavras depois de três letras. Ele não consegue varrer de novo 200.000 palavras entre um toque e outro, então guarda a posição a que chegou em “cat” e, na próxima tecla, dá mais um salto em vez de recomeçar.
O código
Sua vez
Preencha a lacuna.
trie = {"a": {"t": {"$": 1}}}
node = trie
for ch in "ax":
node = node.get(ch)
if node ___ None:
break
print(node) # NoneMini quiz
1 / 3