Recherche de préfixes et Starts-With

L’avantage déterminant du Trie par rapport à une table de hachage est l’efficacité des requêtes de préfixe. Une requête de préfixe répond à des questions telles que : « combien de mots stockés commencent par ce préfixe ? », « quels sont tous les mots stockés qui possèdent ce préfixe ? » ou simplement « existe-t-il un mot qui possède ce préfixe ? ». Ces requêtes s’effectuent en O(p), où p est la longueur du préfixe, indépendamment du nombre total de mots stockés — ce qui rend les Trie idéaux pour autocomplete et les suggestions de recherche.

starts_with(prefix) renvoie vrai si un mot stocké commence par le préfixe donné. Parcourez le Trie en suivant chaque caractère du préfixe. Si tous les caractères peuvent être suivis sans rencontrer d’arête manquante, le préfixe existe et au moins un mot commence par celui-ci. L’implémentation est identique à celle de search, sauf que nous renvoyons vrai dès que le parcours est terminé : nous ne vérifions pas is_end.

Pour implémenter autocomplete, parcourez le Trie jusqu’au nœud qui termine le préfixe, puis effectuez un DFS ou un BFS depuis ce nœud afin de recueillir tous les mots qui en partent. Ajoutez le préfixe au début de chaque suffixe recueilli pour reconstruire les mots complets. Cette opération s’effectue en O(p + W), où W est le nombre total de caractères dans tous les mots correspondants.

Pour une autocomplete triée, parcourez les enfants dans l’ordre alphabétique pendant le DFS, en itérant sur sorted(node.children.items()). Comme les enfants sont stockés dans un dictionnaire, cela ajoute une surcharge de O(taille de l’alphabet × profondeur), mais garantit des résultats classés dans l’ordre lexicographique. Un Trie fondé sur un tableau parcourt toujours les enfants dans l’ordre alphabétique, puisque les indices 0 à 25 sont ordonnés.

Pour obtenir les meilleures K suggestions selon la fréquence, ajoutez à chaque nœud un compteur du nombre de fois où le mot qui se termine à cet endroit a été recherché. Lors de la collecte des suggestions, utilisez un tas max de taille k. Cela réduit l’ensemble des résultats du DFS, en O(W), à O(k), sans matérialiser toutes les correspondances. Les moteurs de recherche réels combinent le parcours des préfixes d’un Trie avec des données de fréquence pour fournir rapidement des suggestions pertinentes.

Le problème LeetCode 208, « Implémenter un Trie (arbre de préfixes) », demande exactement : insert(word), search(word), qui renvoie un booléen de correspondance exacte, et startsWith(prefix), qui renvoie un booléen de correspondance de préfixe. Il s’agit de l’implémentation canonique d’un Trie. N’oubliez pas : search exige is_end=True ; startsWith exige seulement que le chemin du préfixe existe.

Une astuce élégante consiste à stocker le Trie sous forme de dictionnaires imbriqués, avec une clé sentinelle spéciale comme '#' pour marquer la fin des mots, ce qui élimine le besoin d’une classe TrieNode. Cette solution est compacte et adaptée aux entretiens, mais légèrement moins lisible que des objets TrieNode explicites. Les deux implémentations sont acceptables ; la version avec dictionnaire est plus rapide à écrire sous pression.

Pour trouver le préfixe commun le plus long d’une liste de chaînes, insérez toutes les chaînes dans le Trie, puis parcourez celui-ci depuis la racine en suivant l’unique chemin qui existe tant que : (1) le nœud courant possède exactement un enfant et (2) is_end vaut faux. Arrêtez-vous dès que l’une de ces conditions n’est plus satisfaite. Le chemin suivi est le préfixe commun le plus long.

Remplacer les mots (LeetCode 648) : étant donné un dictionnaire de mots racines et une phrase, remplacez chaque mot de la phrase par la racine correspondante la plus courte du dictionnaire. Insérez toutes les racines dans un Trie. Pour chaque mot de la phrase, parcourez le Trie jusqu’à trouver la fin d’une racine, puis renvoyez cette racine comme remplacement. Si aucune racine ne correspond, conservez le mot d’origine. Cette méthode s’exécute en O(nombre total de caractères), contre O(n × m) pour la force brute.

Somme de mappage (LeetCode 677) : insérez des paires clé-valeur et renvoyez la somme de toutes les valeurs dont les clés possèdent un préfixe donné. Ajoutez à chaque TrieNode un champ val. Pour insert, parcourez le Trie jusqu’à la fin et définissez la valeur ; pour les requêtes de somme, parcourez le Trie jusqu’au nœud qui termine le préfixe et calculez avec DFS la somme de tous les champs val situés en dessous. Vous pouvez aussi stocker la somme cumulée dans chaque nœud lors de l’insertion afin d’obtenir des requêtes en O(p).

Dans les systèmes de saisie semi-automatique en production, renvoyer tous les mots correspondant à un préfixe est impraticable lorsque des milliers de mots correspondent. Utilisez plutôt un tas maximal de taille k pendant le parcours DFS : conservez les k mots ayant les scores les plus élevés parmi ceux trouvés jusqu'à présent. Arrêtez prématurément les branches du parcours DFS si elles ne peuvent manifestement pas contenir un mot parmi les k meilleurs (élagage selon une borne supérieure du score). Cela donne une complexité de O(p + k × log k) par requête pour k suggestions — bien meilleure que la collecte de toutes les correspondances.

Dans cette leçon, vous avez appris que starts_with parcourt le chemin du préfixe et renvoie True s'il existe — aucune vérification de is_end n'est nécessaire, que la saisie semi-automatique par DFS collecte tous les mots à partir du nœud terminal du préfixe en ajoutant des caractères au fur et à mesure de la descente, et que l'ajout de compteurs ou de valeurs aux nœuds permet d'effectuer des requêtes de somme et de proposer les k meilleures suggestions. Ensuite, nous ajouterons la recherche avec caractères génériques et expressions régulières dans le trie.