O padrão em 30 segundos
Árvore de prefixos: cada nó é um caractere, cada caminho da raiz é um prefixo. Busca e inserção em O(comprimento da palavra), independentemente de quantas palavras existam. Autocomplete, dicionários com wildcard, word search otimizado.
Como reconhecer na hora
- "Prefixo" no enunciado: startsWith, autocomplete
- Muitas buscas de palavras contra um dicionário fixo
- Wildcard matching (busca com "." valendo qualquer letra) → DFS no trie
onde todo mundo erra · anotado no caderno
Esquecer o marcador de fim de palavra ("isWord") e não conseguir distinguir prefixo de palavra completa: "app" vs "apple". É um boolean no nó; sem ele o trie inteiro está errado.
Complexidade típica: Inserir/buscar O(L) com L = tamanho da palavra; espaço é o preço (um mapa por nó).
Os 3 problemas da categoria
| Problema | Dificuldade | Nível no app |
|---|---|---|
| Implement Trie (Prefix Tree) | medium | nível 2 · core |
| Design Add and Search Words | medium | nível 2 · core |
| Word Search II | hard | nível 4 · core |
No app, esses 3 problemas entram numa trilha de 4 níveis com marcação do que mais cai em entrevista, e você registra tentativa, revisão e domínio de cada um.
Abrir a trilha NeetCode no app