O básico de tries
Passo 1 de 10
Uma trie (árvore de prefixos) vazia é um único nó raiz. Toda palavra começa seu caminho aqui.
A ideia
Uma trie (árvore de prefixos) soletra as palavras em vez de guardá-las inteiras. Cada aresta carrega um caractere, então o caminho que desce da raiz é um prefixo. Palavras que compartilham um prefixo compartilham esses nós.
Uma flag por nó marca “uma palavra termina aqui” — sem ela, você não distingue a palavra car do prefixo dentro de cart.
Exemplo do mundo real
O velho fichário de uma biblioteca: gavetas etiquetadas A–C, dentro delas divisórias para a segunda letra, depois para a terceira. Ninguém guarda o título duas vezes só porque dois livros começam com “Ca” — você percorre as etiquetas e todo livro atrás daquela divisória é um acerto.
O código
Sua vez
O que isto imprime?
root = {}
for word in ["do", "dorm"]:
node = root
for ch in word:
node = node.setdefault(ch, {})
node["$"] = True
print(sorted(root["d"]["o"]))Mini quiz
1 / 3