C ++ - Comment savoir efficacement si une chaîne d'un vecteur peut être assemblée à partir d'un ensemble de lettres

Vous pouvez également stocker les chaînes avec des caractères triés dans l'ordre asciibétique dans un STD :: Set, puis trier les lettres du lecteur dans le même ordre et recherchez la carte pour chaque sous-chaîne des lettres du joueur.

Que diriez-vous de garder les paires {mot du dictionnaire, une chaîne constituée des mêmes lettres mais en ordre croissant (tri)}

Trier le vecteur de ces paires en fonction de la deuxième chaîne et comparez à l'aide de la recherche binaire avec une chaîne composée de lettres triées de la main des joueurs.

sonne comme une variante du sous-ensemble Sum Problème: http://fr.wikipedia.org/wiki / Subset_sum_problem

Peut-être que certains des algorithmes décrits vous aideraient.

Il y a eu de nombreux papiers et des questions sur Scrabble sur ce site.

Il existe de nombreuses stratégies disponibles. P>

La représentation de votre dictionnaire est inadéquate, il existe de nombreuses méthodes intelligentes disponibles. Par exemple, vérifiez ce qu'une trie est sur wikipedia. P>

Utilisation de celui-ci, vous pouvez implémenter un algorithme de retour en arrière pour déterminer rapidement quels mots que vous pouvez former. P>

 1. I have a 'a' (but 'a' is not a word)
 2. I have a 'p' (but 'ap' is not a word)
 3. I don't have any 'e' so I can't go further, let's backtrack
 4. I don't have any 's' so...
 5. I have a 'g', but it's not a word
 6. I have a 'u', but 'gu' is not a word
 7. I have a 'm' and 'gum' is a word, I store it somewhere, I can't go further

Il y a déjà de bonnes réponses ici, et je pense qu'une trie est probablement la bonne façon d'y aller, mais c'est un problème intéressant, je vais donc lancer dans mes deux cents 'Worthing ...

L'approche naïve serait de générer toutes les permutations des lettres disponibles et de tous les sous-ensembles distincts, puis recherchez chaque mot potentiel dans le dictionnaire. Le problème est que, bien qu'il ne soit pas difficile de le faire, il existe un nombre étonnamment important de mots potentiels, et la plupart d'entre eux sont invalides.

du côté positif, la vérification du dictionnaire peut être accélérée avec une recherche binaire ou quelque chose de similaire. Du côté négatif, vous le feriez tant de fois que le programme serrait à une halte pour de longues listes de lettres.

Nous avons définitivement besoin de prétraitement du dictionnaire pour le rendre plus utile et ce dont nous avons vraiment besoin, c'est d'avoir un moyen d'exclure rapidement la plupart des matchs potentiels, même si la méthode présente des faux positifs occasionnels.

Un moyen de faire cela serait de représenter quelles lettres utilisées par un mot dans une carte de bit. En d'autres termes, précalculer un nombre 32 bits pour chaque mot dans le dictionnaire, où chaque bit est défini si la lettre correspondante de l'alphabet est utilisée dans le mot au moins une fois. Cela vous permettrait de trouver tous les mots potentiels en effectuant une analyse linéaire du dictionnaire et de ne conserver que celles qui utilisent uniquement des lettres que vous avez disponibles. Je soupçonne que, avec un peu d'intelligence et d'indexation, vous pouvez faire mieux que linéaire.

des candidats que vous trouvez, certains auront besoin de plus d'instances d'une lettre que de votre disposition. Celles-ci seront donc de faux positifs. Cela signifie que vous devez faire un chèque final sur tous les candidats que vous avez générés pour éliminer les quasi-hits. Il existe de nombreuses façons de le faire, mais l'un des plus simples consiste à parcourir votre liste de lettres et à remplacer la première occurrence de cette lettre dans le mot potentiel avec un tiret. Lorsque vous avez terminé, si le mot potentiel a quelque chose que des tirets, c'est un échec. Une solution plus élégante, mais pas nécessairement plus rapide, serait de générer une gamme de fréquences de lettre et de les comparer.

Encore une fois, je pense que les essais sont probablement la voie à suivre, mais j'espère que ces idées vous sont utiles.

modifier

Permettez-moi de jeter un exemple de la manière dont vous pourriez faire mieux qu'une recherche linéaire complète de la recherche initiale: utilisez le radix. Gardez un index simple qui vous permet de rechercher le premier mot qui commence par une lettre donnée. Ensuite, lorsque vous faites la recherche, sautez tous les mots qui commencent par une lettre que vous n'avez pas. Ce n'est pas un gigantesque vitesse, mais c'est une amélioration.