Recherche avec caractères génériques et expressions régulières dans un trie

La recherche standard dans un trie gère les caractères exacts. La recherche avec caractère générique ajoute un caractère spécial '.' qui correspond à n'importe quel caractère unique. Lorsque nous rencontrons un '.' pendant la recherche, au lieu de suivre un enfant précis, nous devons essayer tous les enfants — il s'agit d'une ramification. C'est l'idée centrale derrière LeetCode 211 « Concevoir une structure de données pour ajouter et rechercher des mots ». Chaque '.' multiplie le nombre de chemins de recherche par le nombre d'enfants à ce niveau.

Implémentez la recherche avec caractère générique à l'aide d'un assistant DFS récursif. Pour chaque caractère du motif : s'il s'agit d'un caractère littéral, suivez l'enfant correspondant (ou renvoyez False s'il est absent) ; s'il s'agit de '.', appelez récursivement tous les enfants et renvoyez True si l'un d'eux réussit. À la fin du motif, renvoyez node.is_end.

Lorsqu'un '.' est rencontré, nous appelons any(dfs(child, i+1) for child in node.children.values()). Le générateur any() utilise une évaluation avec arrêt anticipé : il s'arrête dès qu'un enfant renvoie True. Cela évite les explorations inutiles. Dans le pire des cas (motif composé uniquement de '.'), nous explorons tous les chemins — la complexité est de O(26^k), où k est le nombre de points, ce qui rend des motifs comme '....' coûteux pour les tries volumineux.

Une approche itérative utilise une file de paires (node, index). Commencez par (root, 0). Pour chaque paire, si index == len(word) et node.is_end, renvoyez True. Sinon, traitez le caractère courant : pour '.', ajoutez tous les enfants à la file ; pour un caractère littéral, ajoutez uniquement l'enfant correspondant. Il s'agit essentiellement d'un parcours BFS des chemins du trie.

Pour un motif sans caractères génériques, la recherche est en O(m). Pour un motif contenant k caractères génériques, le pire cas est O(26^k × m) — une complexité exponentielle par rapport au nombre de caractères génériques. En pratique, les caractères génériques sont généralement peu nombreux et le trie est peu profond, les performances sont donc acceptables. Pour les motifs entièrement composés de caractères génériques (par exemple, correspondant à tous les mots de longueur k), la recherche dégénère en un parcours complet du trie.

Passer aux expressions régulières complètes (par exemple, '*' correspondant à zéro caractère ou davantage) nécessite une gestion différente. Un '*' peut correspondre à n'importe quel suffixe ; lorsque nous le rencontrons, nous devons essayer tous les chemins du trie à partir du nœud courant. La véritable recherche par expressions régulières dans un trie est complexe — elle est généralement réservée aux constructions NFA/DFA. En entretien, les caractères génériques uniques ('.') constituent le motif standard.

La correspondance de motifs glob avec '?' (n'importe quel caractère unique) et '*' (n'importe quelle séquence, y compris une séquence vide) peut être implémentée avec DP. Si vous l'implémentez dans un trie, '?' correspond à une ramification sur un seul niveau (comme '.') et '*' correspond à un parcours DFS sur plusieurs niveaux. L'approche DP combinée est la suivante : dp[i][j] = True si pattern[0..i] correspond à string[0..j]. En entretien, l'intervieweur précise généralement quelle variante doit être implémentée.

Les tries avec caractères génériques sont utilisés dans les tables de routage IP, où '*' joue le rôle de caractère générique de préfixe. Un routeur stocke des préfixes de routes comme '192.168.*' et les compare aux adresses entrantes. La correspondance par préfixe le plus long (la route la plus spécifique l'emporte) est implémentée en parcourant le trie aussi profondément que possible et en utilisant la dernière correspondance rencontrée. Il s'agit d'une application concrète des opérations de préfixe et de caractère générique sur les tries.

Lorsqu'un nœud du trie n'a aucun enfant (c'est une feuille) et que is_end = False, toute recherche qui l'atteint renvoie False. Pendant la recherche avec caractère générique, ignorer ces nœuds terminaux sans issue avant l'appel récursif permet d'élaguer des appels inutiles. Le maintien d'un word_count dans chaque nœud (nombre total de mots dans le sous-arbre) permet d'ignorer tout un sous-arbre si aucun mot ne peut respecter les contraintes de longueur du motif restant.

Une classe WordDictionary claire et prête pour un entretien, qui combine l'insertion et la recherche avec le caractère générique point dans une seule classe. Il s'agit de l'implémentation exacte attendue pour LeetCode 211. La recherche récursive avec any() à arrêt anticipé est concise et montre clairement la logique de ramification aux personnes qui mènent l'entretien.

dict.setdefault(key, default) renvoie la valeur associée à key si celle-ci est présente ; sinon, il insère default et le renvoie. L'utilisation de node.setdefault(c, {}) lors de l'insertion élimine la vérification if-else : elle crée le dictionnaire enfant s'il est absent et le renvoie dans tous les cas. L'insertion devient ainsi un parcours sur une seule ligne : for c in word: node = node.setdefault(c, {}). Une solution claire et idiomatique en Python.

Testez votre compréhension des concepts de structures de données et d'algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.

Dans cette leçon, vous avez appris que le caractère générique '.' nécessite une ramification vers tous les enfants à la position correspondante à l'aide d'un DFS récursif, que l'utilisation de any() avec un générateur fournit une évaluation avec arrêt anticipé pour mettre fin rapidement à la recherche, et que setdefault permet une insertion compacte du trie sur une seule ligne. Ensuite, nous combinerons trie et retour arrière pour résoudre Word Search II — trouver plusieurs mots simultanément sur une grille en deux dimensions.