Busca de palavras II: trie + retrocesso em uma grade
Insira todas as palavras-alvo em uma trie e execute retrocesso com DFS em um tabuleiro bidimensional para encontrar simultaneamente todas as palavras válidas em O(m × n × 4^L).
Busca de palavras II: trie + retrocesso em uma grade é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 4 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 problema da Busca de Palavras II
Busca de Palavras II (LeetCode 212): dada uma matriz m × n de caracteres e uma lista de palavras, encontre todas as palavras que podem ser formadas por células sequencialmente adjacentes (horizontal ou verticalmente), sendo que cada célula pode ser usada apenas uma vez. Isso é mais difícil do que a Busca de Palavras I (uma única palavra), pois precisamos encontrar todas as palavras correspondentes simultaneamente — executar ingenuamente a Busca de Palavras I para cada palavra resulta em O(W × m × n × 4^L), o que é lento demais.
Por que combinar árvore de prefixos e retrocesso?
Inserir todas as palavras-alvo em uma árvore de prefixos e depois executar um retrocesso com DFS na matriz permite procurar todas as palavras simultaneamente. Em cada célula da matriz, em vez de verificar "este caminho forma a minha palavra-alvo?", verificamos "este caminho corresponde a um prefixo na árvore de prefixos?". Assim que um prefixo da árvore de prefixos deixa de corresponder, podamos todo o ramo do DFS — evitando trabalho redundante entre todas as palavras que compartilham esse prefixo.
Construindo a árvore de prefixos a partir da lista de palavras
Insira todas as palavras em uma árvore de prefixos. Armazene a palavra completa no nó folha (em node.word) em vez de apenas um booleano; assim, quando uma correspondência completa for encontrada durante o retrocesso, poderemos adicionar imediatamente a palavra aos resultados sem reconstruí-la caractere por caractere.
class TrieNode:
def __init__(self):
self.children = {}
self.word = None # stores the complete word if this is an end node
def build_trie(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.word = word # mark complete word here
return root
root = build_trie(['eat','oath','ot'])
print('Trie built with', len(root.children), 'root children')Retrocesso com DFS na matriz
Inicie um DFS a partir de cada célula da matriz. A cada etapa: (1) verifique se o caractere da célula atual existe como filho no nó atual da árvore de prefixos; (2) se existir, marque a célula como visitada (defina seu valor como um marcador, como '#') e faça a recursão nos 4 vizinhos; (3) após a recursão, restaure a célula (desmarque-a). Quando um nó da árvore de prefixos tiver um word diferente de None, adicione-o aos resultados e defina-o como None para evitar duplicates.
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def findWords(board, 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.word = word
m, n = len(board), len(board[0])
result = []
def dfs(i, j, node):
c = board[i][j]
if c not in node.children:
return
next_node = node.children[c]
if next_node.word:
result.append(next_node.word)
next_node.word = None # avoid duplicates
board[i][j] = '#' # mark visited
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs(ni, nj, next_node)
board[i][j] = c # restore
for i in range(m):
for j in range(n):
dfs(i, j, root)
return result
board = [['o','a','a','n'],['e','t','a','e'],['i','h','k','r'],['i','f','l','v']]
words = ['oath','pea','eat','rain']
print(findWords(board, words)) # ['oath','eat']Análise de complexidade
Tempo: O(m × n × 4^L), onde L é o comprimento máximo de uma palavra. Para cada uma das células iniciais m×n, o DFS explora até 4^L caminhos. A árvore de prefixos poda os caminhos que não correspondem a nenhum prefixo de palavra, portanto, na prática, é muito mais rápida. A construção da árvore de prefixos é O(W × L), onde W é o número de palavras. Espaço: O(W × L) para a árvore de prefixos, além de O(L) para a profundidade da pilha de recursão.
Poda: removendo nós folha após encontrar uma palavra
Depois de encontrar uma palavra, remova o nó folha da árvore de prefixos (em vez de apenas anular a palavra) se ele não tiver filhos. Isso impede que ramos sem saída sejam visitados novamente em chamadas posteriores de DFS. Quando os filhos de um nó ficam vazios depois que a palavra é encontrada, remova esse nó do dicionário de filhos do pai. Essa otimização é significativa quando muitas palavras compartilham prefixos longos.
def dfs_with_pruning(i, j, node, board, m, n, result):
c = board[i][j]
if c not in node.children:
return
next_node = node.children[c]
if next_node.word:
result.append(next_node.word)
next_node.word = None
board[i][j] = '#'
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs_with_pruning(ni, nj, next_node, board, m, n, result)
board[i][j] = c
# Prune: if the node has no more children and no word, remove it
if not next_node.children and not next_node.word:
del node.children[c]
print('Leaf pruning removes exhausted trie branches during search')Por que armazenar word no nó é melhor
Armazenar a palavra completa no nó folha da árvore de prefixos (em vez de reconstruí-la a partir do caminho do DFS) oferece duas vantagens: (1) recuperação da palavra em O(1) quando uma correspondência é encontrada, em vez da reconstrução do caminho em O(L); (2) definir node.word = None depois de encontrar a palavra proporciona uma desduplicação limpa em O(1), sem a necessidade de um conjunto separado de resultados. Em particular, na Busca de Palavras II, evitar duplicatas é importante porque, teoricamente, a mesma palavra pode ser encontrada por caminhos diferentes.
Marcando células visitadas no próprio lugar
Em vez de usar um conjunto visited separado (que exigiria espaço O(m × n) para cada caminho do DFS), marque as células no próprio lugar, substituindo seu caractere por um marcador, como '#'. Depois que o DFS retornar, restaure o caractere original. Esta técnica: (1) usa espaço extra O(1) por célula; (2) impede automaticamente novas visitas durante um único caminho; (3) é totalmente transparente para o percurso da árvore de prefixos, pois '#' nunca estará na árvore de prefixos.
Casos-limite a tratar
Casos-limite importantes: (1) palavras duplicadas na lista de palavras — armazene-as em um conjunto ou use o truque node.word = None para evitar duplicatas nos resultados; (2) palavras muito longas que excedem as dimensões da matriz — elas não podem ser formadas, mas o DFS trata isso naturalmente ao ficar sem células adjacentes; (3) matriz de uma única célula — apenas palavras de um caractere podem ser encontradas; (4) a mesma palavra pode ser encontrada por caminhos diferentes — o truque node.word = None impede a contagem dupla.
Comparação com a abordagem ingênua
Abordagem ingênua: para cada uma das W palavras, execute a Busca de Palavras I: O(W × m × n × 4^L). Com a árvore de prefixos, todas as palavras são pesquisadas simultaneamente: O(m × n × 4^L), independentemente de W. Para W=1000 palavras de comprimento 10 em uma matriz 10×10, a abordagem ingênua é 1000 vezes mais lenta do que a árvore de prefixos. A árvore de prefixos atua como um filtro de prefixos compartilhado que distribui o custo entre todas as palavras — um exemplo clássico do uso de uma estrutura de dados para obter uma melhoria assintótica.
Resumo da solução completa
Solução completa para a Busca de Palavras II: construa uma árvore de prefixos com as palavras e armazene a cadeia de caracteres da palavra na folha. Para cada célula da matriz, execute um DFS: verifique se o caractere atual existe no nó atual da árvore de prefixos, marque a célula como '#', faça a recursão nos 4 vizinhos e restaure a célula. Quando node.word não for nulo, adicione-o aos resultados e anule-o. Opcionalmente, pode podar os ramos vazios da árvore de prefixos depois de usá-los. Retorne a lista de resultados. Tempo: O(m×n×4^L), Espaço: árvore de prefixos O(W×L) + recursão O(L).
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def findWords_final(board, words):
root = TrieNode()
for word in words:
node = root
for c in word:
node = node.children.setdefault(c, TrieNode())
node.word = word
m, n = len(board), len(board[0])
result = []
def dfs(i, j, node):
c = board[i][j]
child = node.children.get(c)
if not child:
return
if child.word:
result.append(child.word)
child.word = None
board[i][j] = '#'
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs(ni, nj, child)
board[i][j] = c
if not child.children:
del node.children[c]
for i in range(m):
for j in range(n):
dfs(i, j, root)
return resultVerificaçã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: a Busca de Palavras II usa uma árvore de prefixos para permitir a busca simultânea de várias palavras, com poda de prefixos compartilhados, armazenar a cadeia de caracteres da palavra na folha da árvore de prefixos permite recuperá-la em O(1) e desduplicá-la facilmente definindo-a como None depois de encontrá-la e marcar as células visitadas no próprio lugar evita espaço extra O(m×n) para cada caminho do DFS. Isso conclui o curso de Árvores de Prefixos e Algoritmos de Cadeias de Caracteres — você dominou uma das estruturas de dados mais poderosas e específicas para cadeias de caracteres usadas em entrevistas.
Perguntas Frequentes
A aula “Busca de palavras II: trie + retrocesso em uma grade” é grátis?
Sim — o texto completo de “Busca de palavras II: trie + retrocesso em uma grade” é 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 de palavras II: trie + retrocesso em uma grade”?
Insira todas as palavras-alvo em uma trie e execute retrocesso com DFS em um tabuleiro bidimensional para encontrar simultaneamente todas as palavras válidas em O(m × n × 4^L). 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 4 de 4.
Quanto tempo leva a aula “Busca de palavras II: trie + retrocesso em uma grade”?
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