Comment puis-je trouver des mots dans une matrice de lettres
C'est une autre question que j'avais posée dans l'entretien téléphonique:
Donné un dictionnaire et mots croisés(2d matrice de caractères) trouver tous les mots du dictionnaire qui peut être trouvé dans les mots croisés.
Tout ce que je pouvais penser était de hachage le dictionnaire, trouver tous les mots possibles dans les mots croisés et de recherche de la table de hachage. Je ne pouvais pas optimiser tout cela.
Dois admettre que Microsoft les questions d'entrevue sont difficiles 🙁
Merci de me donner les lignes de réfléchir.
source d'informationauteur Edward
Vous devez vous connecter pour publier un commentaire.
Comment sur:
Je ne pense pas qu'un hash serait très utile d'optimisation.
La solution la plus appropriée dépend beaucoup sur les contraintes que vous vous attendez à être confrontés. Quelle est la taille de votre dictionnaire? Quelle est la taille de votre croisés.
Je vous suggère de prendre un coup d'oeil à Suffixe arbres. Vous pouvez insérer tous les mots du dictionnaire en un seul. Ensuite, la recherche de suffixe de l'arbre pour les lignes, colonnes et diagonales. Pour les lignes, lancer une recherche à partir de la racine de l'arbre correspondant à la première lettre de chaque ligne et parcourir l'arbre que vous passer à travers la ligne. Faire de même de droite à gauche si nécessaire. Même histoire pour les colonnes et les diagonales.
La construction de l'arbre est O(N) et consomme O(N), où N est la taille de votre dictionnaire des caractères. La recherche prendra alors O(PQ) le temps, où vos mots croisés est de taille PxQ. Donnant généralement un temps d'exécution de O(N+PQ) et de l'espace de O(N).
La chose est, cependant, suffixe arbres sont une douleur à mettre en œuvre. Ils sont vraiment. Donc, vous préférerez peut-être de s'installer pour un simple Triequi vous donnera un total d'exécution de O(N+PQ(max(P,Q)).
Cette question est exactement la façon dont on pourrait jouer Boggle.
Cette dernière question, dans plus de suffisamment RÉPONSES à CETTE QUESTION.
Avoir du plaisir...
Ce qui était incorrect avec votre réponse?
Un dictionnaire est trié donc je pense que je ferais organiser les mots du dictionnaire dans un préfixe trie. Ce serait de l'aide car il y a probablement beaucoup de mots où le préfixe est aussi un mot. Le tri permet de (très peu) avec le temps de génération.
Puis marcher les mots croisés, regardant de tous les mots possibles. Comme vous l'avez extrait les caractères d'un potentiel mot, que vous marchez dans la trie - de sorte que vous allez trouver le premier mot commençant par un certain ensemble de caractères, mais aussi d'être au bon endroit pour continuer à trouver d'autres mots commençant par les mêmes caractères
Supposons que le dictionnaire contient n mots de longueur moyenne ket la matrice contient des m2 caractères.
Temps Total: O(max(knm3))
Réaliste mot-recherches, la longueur moyenne des mots trouvés dans la matrice est plus comme k que comme mde sorte que les délais seraient prises en O(k max(nm2)).
Je voudrais compiler le dictionnaire dans un DFA qui reconnaît des mots dans le dictionnaire, puis l'exécuter sur les lignes et les colonnes et les diagonales de la lettre de la matrice. Devrait être
O(m+n)
oùm
est la longueur du dictionnaire de caractères etn
est la zone (w*h) de la matrice.