O padrão em 30 segundos
Árvore de prefixos: cada nó é um caractere, cada caminho da raiz é um prefixo. Inserção e busca exata percorrem O(comprimento da palavra) nós, independentemente de quantas palavras existam. Wildcards e buscas em tabuleiro podem explorar vários caminhos. 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
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 e buscar uma palavra exata custam O(L), com L = tamanho da palavra e acesso O(1) aos filhos. Com d wildcards e alfabeto de tamanho σ, a busca pode custar O(L × σ^d); se d e σ forem constantes (como os até dois pontos no exercício Design Add and Search Words), isso continua O(L). O trie ocupa O(S), com S = soma dos comprimentos das palavras inseridas.
Os 3 problemas da categoria
| Problema | Dificuldade | Nível no VagaGringa |
|---|---|---|
| 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 VagaGringa, 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