[Algo C++] Anagrammes Résolu/Fermé

Question

Bonjour,

Je suis en train de faire un programme qui recherche des anagrammes (j'entends par anagramme un mot qui peut s'écrire avec les lettres d'un autre). Après de nombreux essais je pensais avoir définitivement trouvé comment écrire ma fonction principale isAnagram, mais je viens de terminer le reste du code et je m'aperçois qu'en fait elle me donne des faux positifs (et peut-être des faux négatifs mais c'est moins évident à déterminer)

Si quelqu'un pouvait regarder mon code et me dire comment le corriger... Merci !// stringD.h

class stringD
{
private:
    s1,s2:std::string;

// s1 et s2 ne contiennent que des lettres majuscules entre 'A' et 'Z'
// s2 contient les mêmes lettres que s1 mais triées dans l'ordre alphabétique

public:
    size_t size(void);
    bool isAnagram(stringD s);
};

// stringD.cpp

bool stringD::isAnagram(stringD s) // this* est-il écrit avec les lettres de s ?
{
    if (size()>s.size()) return false;

    for (unsigned i=0,j=0; j<s.size(); i++, j++)
    {
        while (s.s2[j]<s2[i])
            j++;

        if (s2[i]!=s.s2[j])
            return false;
    }
    return true;
}Un exemple de faux positif :x.s1="LETTRES", x.s2="EELRSTT"
y.s1="LUTTEUR", y.s2="ELRTTUU"

bool b=x.isAnagram(y); // b==true !?

Char Snipeur · Answer

je ne comprend pas ton algorithme.
Pourtant, si tu as les lettres du mot trié alphabétiquement, il suffit de voir si les chaine s2 sont identiques.
Deux mots sont anagramme lorsqu'ils contiennent les même lettres. Et si ils contients les même lettres, leur trie alphabétique est le même.
ta fonction devrais être juste :
return s2==s.s2;

KX · Answer

Je suis d'accord sur la vraie définition d'un anagramme.
Cependant comme je l'ai dit j'entends par anagramme un mot qui peut s'écrire avec les lettres d'un autre, par exemple si je joue au Scrabble, j'ai 7 lettres et je cherche tous les mots que je puisse avoir avec ces 7 lettres.
Il y aura donc dans mes résultats d'une part des anagrammes mais aussi des mots plus courts...

Le problème c'est que mon algorithme renvoie true à des mots this* qui ne contiennent pas les lettres des s.
Ce qui me laisse encore plus perplexe, c'est que avec le même mot, si je lance plusieurs fois de suite la recherche sur le dictionnaire entier, il ne me trouve pas toujours les même faux positifs. C'est à dire qu'avec le mot "LETTRES" j'ai parfois 46 résultats positifs dans le dictionnaire, parfois 64, parfois entre les deux... Donc bien sûr les vrais "anagrammes" apparaissent toujours mais les faux positifs semblent aller et venir de façon aléatoire !

Sur l'idée mon algorithme compare des mots qui peuvent donc être de taille différente this* de taille <= à s d'où ma première ligne. Par exemple, "BON" est - selon ma définition - anagramme de "BONJOUR".
La recherche compare donc this->s2="BNO" et s.s2="BJNOORU.
Je parcours donc les deux mots en comparant les deux première lettres, ici égales -> je compare les deux deuxièmes, différentes -> j'incrémente mon "curseur" sur s.s2; pour comparer O et O, en excluant donc la lettre J.
Et je continue jusqu'à la fin, sauf si je trouve par exemple à la place du J un P, ce qui signifierait qu'il n'y ait pas de O dans s, et que this ne peut donc pas être "anagramme" de s.

Il semble que le problème vient de mon return true; final, puisque apparemment mes faux positifs sont composés de lettres de s, et uniquement de lettres supérieurs à la plus grande lettre de s !
Par exemple "LUTTEUR-ELRTTUU" est un faux positif de "LETTRES-EELRSTT" composé avec deux U supérieurs au T qui était la dernière lettre de EELRSTT...

J'arrive bien à analyser l'erreur, mais je ne vois pas comment corriger mon problème, ni même comment le traiter autrement...

KX · Answer

Mon problème ne vient pas de là mais si ça peut aider, voici mon constructeur stringD : #include #include stringD::stringD(const std::string s):s1(s),s2(s) // s doit être un mot en majuscule { std::sort(s2.begin(),s2.end()); }

Char Snipeur · Answer

OK, je comprends mieux. Je n'avais pas compris ta première explication. Comme tes lettres son ordonnées, c'est déjà plus facile. pour que ça soit plus clair, mieux vaut découper ta boucle. bool stringD::isAnagram(stringD s) // this* est-il écrit avec les lettres de s ? { if (size()>s.size()) return false; int j=0; for (unsigned i=0; is.size()) return false; for(int i=0;i

KX · Answer

Merci, ton premier algorithme ne marche pas mieux, mais en partant sur l'idée du deuxième algorithme j'ai réussi à modifier et à obtenir les bons résultats, et de plus avec cette méthode j'ai l'impression que je peux m'abstenir du tri préalable des lettres, ce qui me ferai gagner temps/mémoire lors du chargement du dictionnairebool stringD::isAnagram(stringD s)
{
    if (size()>s.size()) return false;    
    for(unsigned i=0;i<size();++i)
    {
        unsigned pos=s.s2.find(s2[i]);
        if(pos==std::string::npos) return false;
          else s.s2.erase(pos,1);
    }
    return true;
}Merci encore !

[Algo C++] Anagrammes

5 réponses

Discussions similaires