Busca com curingas e expressões regulares em uma trie

A busca padrão em uma árvore de prefixos lida com caracteres exatos. A busca com curingas adiciona um caractere especial '.' que corresponde a qualquer caractere individual. Ao encontrar um '.' durante a busca, em vez de seguir um único filho específico, precisamos tentar todos os filhos — uma ramificação múltipla. Essa é a ideia central por trás do LeetCode 211, "Projetar uma Estrutura de Dados para Adicionar e Buscar Palavras". Cada '.' multiplica os caminhos de busca pelo número de filhos naquele nível.

Implemente a busca com curingas usando um auxiliar recursivo de DFS. Para cada caractere do padrão: se for um caractere literal, siga o filho específico (ou retorne False se ele não existir); se for '.', faça a recursão em todos os filhos e retorne True se algum deles tiver sucesso. No final do padrão, retorne node.is_end.

Quando um '.' é encontrado, chamamos any(dfs(child, i+1) for child in node.children.values()). O gerador any() usa avaliação de curto-circuito — ele para assim que um filho retorna True. Isso evita explorações desnecessárias. No pior caso (um padrão composto apenas por '.'), exploramos todos os caminhos — a complexidade é O(26^k), onde k é o número de pontos, tornando padrões como '....' dispendiosos em árvores de prefixos grandes.

Uma abordagem iterativa usa uma fila de pares (node, index). Comece com (root, 0). Para cada par, se index == len(word) e node.is_end, retorne True. Caso contrário, processe o caractere atual: para '.', enfileire todos os filhos; para um literal, enfileire apenas o filho correspondente. Isso é essencialmente um BFS sobre os caminhos da árvore de prefixos.

Para um padrão sem curingas, a busca é O(m). Para um padrão com k curingas, o pior caso é O(26^k × m) — exponencial em relação ao número de curingas. Na prática, os curingas geralmente são esparsos e a árvore de prefixos é rasa, portanto o desempenho é aceitável. Para padrões compostos inteiramente por curingas (por exemplo, que correspondem a todas as palavras de comprimento k), o processo se reduz ao percurso completo da árvore de prefixos.

Estender a busca para expressões regulares completas (por exemplo, '*' correspondendo a zero ou mais caracteres) exige um tratamento diferente. Um '*' pode corresponder a qualquer sufixo; portanto, ao encontrá-lo, precisamos tentar todos os caminhos da árvore de prefixos a partir do nó atual. A correspondência real de expressões regulares em uma árvore de prefixos é complexa — geralmente fica reservada para construções de NFA/DFA. Em entrevistas, os curingas de um único caractere ('.') são o padrão.

A correspondência de padrões glob com '?' (qualquer caractere individual) e '*' (qualquer sequência, inclusive vazia) pode ser implementada com DP. Se for implementada em uma árvore de prefixos, '?' corresponde a uma ramificação múltipla de um único nível (como '.') e '*' corresponde a um DFS de vários níveis. A abordagem combinada com DP: dp[i][j] = True se pattern[0..i] corresponder a string[0..j]. Normalmente, o entrevistador especifica qual variante deve ser implementada.

Árvores de prefixos com curingas são usadas em tabelas de roteamento de IP, nas quais '*' atua como um curinga de prefixo. Um roteador armazena prefixos de rotas como '192.168.*' e os compara com os endereços recebidos. A correspondência do prefixo mais longo (a rota mais específica vence) é implementada percorrendo a árvore de prefixos o mais profundamente possível e usando a última correspondência encontrada. Esta é uma aplicação real das operações de prefixo e de curinga em árvores de prefixos.

Quando um nó da árvore de prefixos não tem filhos (é uma folha) e is_end = False, qualquer busca que o alcance retorna False. Durante a busca com curingas, ignorar esses nós sem saída antes de fazer a recursão pode podar chamadas desnecessárias. Manter um word_count em cada nó (o total de palavras na subárvore) permite ignorar uma subárvore inteira se nenhuma palavra puder corresponder às restrições de comprimento restantes do padrão.

Uma classe WordDictionary limpa e pronta para entrevistas, que combina inserção e busca com curinga de ponto em uma única classe. Esta é a implementação exata esperada para o LeetCode 211. A busca recursiva com any() de curto-circuito é concisa e demonstra claramente a lógica de ramificação múltipla para os entrevistadores.

dict.setdefault(key, default) retorna o valor de key se ela estiver presente; caso contrário, insere default e o retorna. Usar node.setdefault(c, {}) na inserção elimina a verificação if-else: cria o dicionário filho se ele não existir e o retorna de qualquer forma. Isso transforma a inserção em um percurso de uma única linha: for c in word: node = node.setdefault(c, {}). Limpo e idiomático em Python.

Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação apresentados nesta lição.

Nesta lição, você aprendeu: o curinga '.' exige uma ramificação múltipla para todos os filhos na posição correspondente, usando DFS recursivo, usar any() com um gerador fornece avaliação de curto-circuito para uma interrupção antecipada e setdefault permite uma inserção compacta da árvore de prefixos em uma única linha. A seguir, combinaremos árvore de prefixos e retrocesso para resolver a Busca de Palavras II — encontrando várias palavras simultaneamente em uma matriz bidimensional.