Aujourd'hui, un collègue de travail m'a posé une question. Étant donné une grille de caractères et une liste de mots, il faudrait trouver chaque occurrence de ce mot dans la grille à la fois horizontalement, verticalement et en diagonale.Algorithme de recherche de la grille dans différentes directions
La solution que nous avons trouvée fonctionne et fait l'affaire, mais je suis intéressée de voir comment les esprits des autres se comportent.
Insérez chaque mot de la liste dans un trie ou hash table ou dans un dictionnaire.
Maintenant, pour chaque position dans votre grille, allez horizontalement, verticalement et en diagonale et voyez si vous obtenez des correspondances dans le dictionnaire. Cela devrait vous donner O(N^3) la pire des cas, où N est la taille de la grille. Sinon, je pense que c'est O(N^2*averageWordLength).
Ne serait-ce pas 'O (N * maxWordLength)'? Chaque lettre doit seulement être vérifiée pour être le début d'un mot de longueur 1, 2, 3, ..., maxWordLength. –
Une table de hachage serait un mauvais choix par rapport à un trie. Avec le trie, une fois que vous n'obtenez aucune correspondance pour une chaîne de longueur k, vous pouvez vous arrêter. Avec une table de hachage, vous ne pouvez pas vous arrêter jusqu'à ce que vous ayez essayé toutes les chaînes de longueur n (n est la distance entre votre char et le bord). Par exemple, disons que vous avez la ligne (INTABCDE). Le mot INTEGER est dans votre dictionnaire. Avec le trie, vous essayez d'abord I, qui n'est pas dans le dictionnaire mais est un chemin valide. Vous continuez jusqu'à A, et vous n'êtes plus sur un chemin valide. Vous ne pouvez pas faire cela avec une table de hachage, donc vous seriez obligé de hacher toutes les chaînes possibles. –
@BlueRaja - c'est ce que j'ai dit aussi en fait :). Je voulais dire que 'N' a la taille d'une grille' N x N' (qui a donc 'N^2' éléments totaux). Si vous considérez «N» comme le nombre total d'éléments dans la grille, alors c'est «N» et non «N^2». @Niki - vrai. – IVlad
Les correspondances avant et arrière comptent? –