Busca por prefixo e começa com
Adicione um método starts_with que retorne verdadeiro se alguma palavra inserida compartilhar determinado prefixo e use-o para implementar sugestões de preenchimento automático.
Busca por prefixo e começa com é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
O poder das consultas por prefixo
A principal vantagem da Trie em relação a um mapa de dispersão é a eficiência das consultas por prefixo. Uma consulta por prefixo responde a perguntas como: 'quantas palavras armazenadas começam com este prefixo?', 'quais são todas as palavras armazenadas com este prefixo?' ou simplesmente 'existe alguma palavra com este prefixo?'. Essas consultas são O(p), em que p é o comprimento do prefixo, independentemente do número total de palavras armazenadas — o que torna as Tries ideais para autocomplete e sugestões de pesquisa.
O método starts_with
starts_with(prefix) retorna True se alguma palavra armazenada começar com o prefixo fornecido. Percorra a Trie seguindo cada caractere do prefixo. Se todos os caracteres puderem ser seguidos sem que falte uma aresta, o prefixo existe e pelo menos uma palavra começa com ele. A implementação é idêntica à de search, exceto pelo fato de retornarmos True assim que terminamos a travessia — não verificamos is_end.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def starts_with(self, prefix):
node = self.root
for c in prefix:
if c not in node.children:
return False
node = node.children[c]
return True
t = Trie()
for w in ['hello','help','world','word']:
t.insert(w)
print(t.starts_with('hel')) # True
print(t.starts_with('wor')) # True
print(t.starts_with('xyz')) # FalseAutocomplete: encontrando todas as palavras com um prefixo
Para implementar autocomplete, percorra até o nó final do prefixo e, em seguida, execute um DFS (ou BFS) a partir desse nó para coletar todas as palavras que se ramificam a partir dele. Adicione o prefixo antes de cada sufixo coletado para reconstruir as palavras completas. Essa operação tem complexidade O(p + W), em que W é o número total de caracteres em todas as palavras correspondentes.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def autocomplete(self, prefix):
node = self.root
for c in prefix:
if c not in node.children:
return []
node = node.children[c]
# DFS from prefix end node
results = []
def dfs(n, path):
if n.is_end:
results.append(prefix + path)
for char, child in n.children.items():
dfs(child, path + char)
dfs(node, '')
return results
t = Trie()
for w in ['apple','app','application','apply','apt']:
t.insert(w)
print(t.autocomplete('app')) # ['app','apple','apply','application']Retornando sugestões ordenadas
Para obter autocomplete ordenado, percorra os filhos em ordem alfabética durante o DFS (itere sobre sorted(node.children.items())). Como os filhos são armazenados em um dicionário, isso adiciona uma sobrecarga de O(ALPHABET_SIZE × profundidade), mas garante resultados em ordem lexicográfica. Uma Trie baseada em vetor sempre percorre os filhos em ordem alfabética, pois os índices de 0 a 25 são ordenados.
def dfs_sorted(node, prefix, results):
if node.is_end:
results.append(prefix)
for char in sorted(node.children.keys()): # alphabetical order
dfs_sorted(node.children[char], prefix + char, results)
print('Iterating children in sorted order gives lex-sorted suggestions')As K principais sugestões de autocomplete
Para obter as k sugestões mais frequentes, adicione a cada nó uma contagem de quantas vezes a palavra que termina nele foi pesquisada. Ao coletar as sugestões, use uma fila de prioridade máxima de tamanho k. Isso reduz o conjunto de resultados da busca DFS de O(W) para O(k), sem materializar todas as correspondências. Os mecanismos de pesquisa do mundo real combinam a travessia de prefixos da Trie com dados de frequência para oferecer sugestões rápidas e relevantes.
Implementando a Trie para LeetCode 208
LeetCode 208, 'Implement Trie (Prefix Tree)', exige exatamente: insert(word), search(word), que retorna um booleano de correspondência exata, e startsWith(prefix), que retorna um booleano de correspondência de prefixo. Esta é a implementação canônica de uma Trie. Lembre-se: search exige is_end=True; startsWith exige apenas que o caminho do prefixo exista.
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for c in word:
if c not in node:
node[c] = {}
node = node[c]
node['#'] = True # '#' marks word end
def search(self, word):
node = self.root
for c in word:
if c not in node: return False
node = node[c]
return '#' in node
def startsWith(self, prefix):
node = self.root
for c in prefix:
if c not in node: return False
node = node[c]
return True
t = Trie()
t.insert('apple')
print(t.search('apple')) # True
print(t.search('app')) # False
print(t.startsWith('app')) # TrueUsando '#' como marcador de fim (Trie com dicionário)
Um atalho elegante armazena a Trie como dicionários aninhados, usando uma chave sentinela especial como '#' para marcar o fim das palavras, eliminando a necessidade de uma classe TrieNode. Essa abordagem é compacta e adequada para entrevistas, mas um pouco menos legível que objetos TrieNode explícitos. Ambas as implementações são aceitáveis; a versão com dicionário é mais rápida de escrever sob pressão de tempo.
Maior prefixo comum usando uma Trie
Para encontrar o maior prefixo comum de uma lista de strings, insira todas as strings na Trie e percorra a partir da raiz, seguindo o único caminho existente enquanto: (1) o nó atual tiver exatamente um filho e (2) is_end for False. Pare quando qualquer uma das condições deixar de ser válida. O caminho seguido é o maior prefixo comum.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
def longest_common_prefix(words):
root = TrieNode()
for word in words:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
prefix = []
node = root
while len(node.children) == 1 and not node.is_end:
char, node = next(iter(node.children.items()))
prefix.append(char)
return ''.join(prefix)
print(longest_common_prefix(['flower','flow','flight'])) # 'fl'
print(longest_common_prefix(['dog','racecar','car'])) # ''Problema de substituição de palavras
Substituir palavras (LeetCode 648): dado um dicionário de palavras-raiz e uma frase, substitua cada palavra da frase pela raiz correspondente mais curta do dicionário. Insira todas as raízes em uma Trie. Para cada palavra da frase, percorra a Trie até encontrar o fim de uma raiz — retorne essa raiz como substituição. Se nenhuma raiz corresponder, mantenha a palavra original. Isso executa em O(total de caracteres), em comparação com O(n × m) por força bruta.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
def replaceWords(dictionary, sentence):
root = TrieNode()
for word in dictionary:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def find_root(word):
node = root
for i, c in enumerate(word):
if c not in node.children: break
node = node.children[c]
if node.is_end:
return word[:i+1]
return word
return ' '.join(find_root(w) for w in sentence.split())
print(replaceWords(['cat','bat','rat'], 'the cattle was rattled by the battery'))Problema de pares de soma de mapas
Soma de mapas (LeetCode 677): insira pares chave-valor e retorne a soma de todos os valores cujas chaves tenham determinado prefixo. Adicione a cada TrieNode um campo val. Para insert, percorra até o fim e defina o valor; para consultas de soma, percorra até o nó final do prefixo e calcule, com DFS, a soma de todos os campos val abaixo dele. Como alternativa, armazene a soma cumulativa em cada nó durante a inserção para obter consultas em O(p).
Implementando o preenchimento automático com resultados limitados
Em sistemas de preenchimento automático em produção, retornar todas as palavras que começam com um prefixo é impraticável quando milhares de palavras correspondem a ele. Em vez disso, use um heap máximo de tamanho k durante o percurso DFS: mantenha as k palavras com maior pontuação encontradas até o momento. Interrompa antecipadamente os ramos do DFS se eles não puderem conter uma das k melhores palavras (fazendo poda com base em um limite superior de pontuação). Isso resulta em O(p + k × log k) por consulta para k sugestões — muito melhor do que coletar todas as correspondências.
Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação apresentados nesta lição.
Recapitulação da lição
Nesta lição, você aprendeu: starts_with percorre o caminho do prefixo e retorna True se ele existir — não é necessário verificar is_end, o DFS do preenchimento automático coleta todas as palavras a partir do nó final do prefixo, acrescentando caracteres à medida que desce e aumentar os nós com contagens ou valores permite fazer consultas de soma e obter as k melhores sugestões. A seguir, adicionaremos correspondência com curingas e expressões regulares à árvore de prefixos.
Aprenda Coding Interview Prep com um tutor de IA — grátis
Escreva e execute código real no seu navegador, obtenha ajuda instantânea de um tutor de IA 24/7 e continue de onde parou na web ou no app.
- Cursos
- 90
- Aulas
- 360
Perguntas Frequentes
A aula “Busca por prefixo e começa com” é grátis?
Sim — o texto completo de “Busca por prefixo e começa com” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Busca por prefixo e começa com”?
Adicione um método starts_with que retorne verdadeiro se alguma palavra inserida compartilhar determinado prefixo e use-o para implementar sugestões de preenchimento automático. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.
Quanto tempo leva a aula “Busca por prefixo e começa com”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Classe TrieNode: inserção e busca
- Busca por prefixo e começa com
- Busca com curingas e expressões regulares em uma trie
- Busca de palavras II: trie + retrocesso em uma grade