Pular para o conteúdo

Busca por prefixo

Aula 2 de 4 · 5 min

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)   # None

Mini quiz

1 / 3

Quanto tempo leva para chegar ao nó de um prefixo de tamanho P?