Recherche de mots II : trie et retour arrière sur une grille

Word Search II (LeetCode 212) : étant donné une grille m × n de caractères et une liste de mots, trouvez tous les mots qui peuvent être formés par des cellules adjacentes successives (horizontalement ou verticalement), chaque cellule ne pouvant être utilisée qu'une seule fois. Ce problème est plus difficile que Word Search I (un seul mot), car nous devons trouver tous les mots correspondants simultanément — exécuter naïvement Word Search I pour chaque mot donne une complexité de O(W × m × n × 4^L), ce qui est trop lent.

Insérer tous les mots cibles dans un trie, puis exécuter un retour arrière par DFS sur la grille, permet de rechercher tous les mots simultanément. À chaque cellule de la grille, au lieu de vérifier « ce chemin forme-t-il mon mot cible ? », nous vérifions « ce chemin correspond-il à un préfixe du trie ? ». Dès qu'un préfixe du trie ne correspond plus, nous élaguons toute la branche du DFS — ce qui évite le travail redondant pour tous les mots partageant ce préfixe.

Insérez tous les mots dans un trie. Stockez le mot complet dans le nœud feuille (dans node.word) plutôt qu'une simple valeur booléenne ; ainsi, lorsqu'une correspondance complète est trouvée pendant le retour arrière, nous pouvons immédiatement ajouter le mot aux résultats sans le reconstruire caractère par caractère.

Démarrez un DFS depuis chaque cellule de la grille. À chaque étape : (1) vérifiez que le caractère de la cellule courante existe comme enfant du nœud courant du trie ; (2) si c'est le cas, marquez la cellule comme visitée (remplacez-la par une valeur sentinelle comme '#'), puis appelez récursivement les 4 voisines ; (3) après l'appel récursif, restaurez la cellule (retirez la marque). Lorsqu'un nœud du trie possède un word différent de None, ajoutez-le aux résultats et affectez-lui None pour éviter les doublons.

Temps : O(m × n × 4^L), où L est la longueur maximale d'un mot. Pour chacune des m×n cellules de départ, le DFS explore jusqu'à 4^L chemins. Le trie élague les chemins qui ne correspondent au préfixe d'aucun mot, ce qui le rend beaucoup plus rapide en pratique. La construction du trie est en O(W × L), où W est le nombre de mots. Espace : O(W × L) pour le trie, plus O(L) pour la profondeur de la pile de récursion.

Après avoir trouvé un mot, supprimez le nœud feuille du trie (au lieu de mettre uniquement le mot à null) s'il n'a aucun enfant. Cela empêche de revisiter les branches mortes lors des appels DFS suivants. Lorsque les enfants d'un nœud deviennent absents après la découverte du mot, supprimez ce nœud du dictionnaire des enfants de son parent. Cette optimisation est importante lorsque de nombreux mots partagent de longs préfixes.

Stocker le mot complet dans le nœud feuille du trie (au lieu de le reconstruire à partir du chemin du DFS) présente deux avantages : (1) la récupération du mot en O(1) lorsqu'une correspondance est trouvée, au lieu d'une reconstruction du chemin en O(L) ; (2) affecter node.word = None après avoir trouvé le mot fournit une déduplication claire en O(1), sans nécessiter d'ensemble de résultats distinct. Pour Word Search II en particulier, empêcher les doublons est important, car le même mot pourrait théoriquement être trouvé par des chemins différents.

Au lieu d'utiliser un ensemble visited séparé (qui nécessiterait un espace O(m × n) pour chaque chemin du DFS), marquez les cellules sur place en remplaçant leur caractère par une valeur sentinelle comme '#'. Une fois le DFS terminé, restaurez le caractère d'origine. Cette technique : (1) utilise un espace supplémentaire O(1) par cellule ; (2) empêche automatiquement les revisites au sein d'un même chemin ; (3) reste totalement transparente pour le parcours du trie, puisque '#' ne figurera jamais dans le trie.

Cas limites importants : (1) mots en double dans la liste de mots — stockez-les dans un ensemble, ou utilisez l'astuce node.word = None pour empêcher les doublons dans les résultats ; (2) mots très longs qui dépassent les dimensions de la grille — ils ne peuvent pas être formés, mais le DFS les gère naturellement en arrivant à court de cellules adjacentes ; (3) grille constituée d'une seule cellule — seuls les mots d'un caractère peuvent être trouvés ; (4) même mot trouvable par des chemins différents — l'astuce node.word = None empêche de le compter deux fois.

Approche naïve : pour chacun des W mots, exécuter Word Search I : O(W × m × n × 4^L). Avec le trie, tous les mots sont recherchés simultanément : O(m × n × 4^L), quelle que soit la valeur de W. Pour W=1000 mots de longueur 10 sur une grille de 10×10, l'approche naïve est 1000 fois plus lente que celle utilisant un trie. Le trie agit comme un filtre de préfixes partagé qui répartit le coût entre tous les mots — un exemple classique d'utilisation d'une structure de données pour obtenir une amélioration asymptotique.

Solution complète de Word Search II : construisez un trie avec les mots et stockez la chaîne du mot dans la feuille. Pour chaque cellule de la grille, exécutez un DFS : vérifiez que le caractère courant existe dans le nœud courant du trie, marquez la cellule par '#', appelez récursivement les 4 voisines, puis restaurez la cellule. Lorsque node.word n'est pas nul, ajoutez-le aux résultats et affectez-lui null. Vous pouvez également élaguer les branches vides du trie après leur utilisation. Renvoyez la liste des résultats. Temps : O(m×n×4^L), espace : trie O(W×L) + récursion O(L).

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 Word Search II utilise un trie pour permettre une recherche simultanée de plusieurs mots avec un élagage fondé sur les préfixes partagés, que stocker la chaîne du mot dans la feuille du trie permet de récupérer le mot en O(1) et de supprimer facilement les doublons en lui affectant None après sa découverte, et que le marquage sur place des cellules visitées avec '#' évite d'utiliser un espace supplémentaire O(m×n) pour chaque chemin du DFS. Ce cours sur les tries et les algorithmes de chaînes de caractères est maintenant terminé — vous maîtrisez l'une des structures de données spécialisées dans les chaînes les plus puissantes utilisées en entretien.