View original (French)

C++ Algorithms: Anagrams

Solved
KX Posted messages 19031 Status Moderator -  
KX Posted messages 19031 Status Moderator -
Hello, I am working on a program that searches for anagrams (I mean a word that can be written with the letters of another). After many attempts I thought I had finally found how to write my main function isAnagram, but I just finished the rest of the code and I realize that it actually gives me false positives (and maybe false negatives, though less obvious to determine). If someone could look at my code and tell me how to fix it... Thanks! 
// stringD.h
class stringD {
private:
  s1, s2: std::string; // s1 and s2 contain only uppercase letters between 'A' and 'Z'
                       // s2 contains the same letters as s1 but sorted in alphabetical order
public:
  size_t size(void);
  bool isAnagram(stringD s);
};

// stringD.cpp
bool stringD::isAnagram(stringD s) // is this* written with the letters of 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;
}
An example of a false positive: 
x.s1 = "LETTRES", x.s2 = "EELRSTT"
y.s1 = "LUTTEUR", y.s2 = "ELRTTUU"
bool b = x.isAnagram(y); // b == true !?
-- Configuration: Windows Vista SP2 / Qt 4.5.2

5 answers

  1.
    KX Posted messages 19031 Status Moderator 3 020
     
    My problem doesn’t come from there, but if it helps, here is my stringD constructor: 
     #include <string> #include <algorithm> stringD::stringD(const std::string s):s1(s),s2(s) // s must be a word in uppercase { std::sort(s2.begin(),s2.end()); }

    --
    Confidence does not exclude scrutiny
    1
  2. Char Snipeur Posted messages 10112 Registration date   Status Contributor Last intervention   1 331
     
    I don’t understand your algorithm.
    However, if you have the letters of the word sorted alphabetically, it’s enough to check if the strings s2 are identical.
    Two words are anagrams when they contain the same letters. And if they contain the same letters, their alphabetical sort is the same.
    your function should be just:
    return s2==s.s2;
    --
    Greetings! (you should understand that I ALWAYS AM RIGHT)
    Char Snipeur
    0
  3. KX Posted messages 19031 Status Moderator 3 020
     
    I agree with the true definition of an anagram. However, as I said, by anagram I mean a word that can be written with the letters of another word; for example, if I’m playing Scrabble, I have 7 letters and I’m looking for all the words I can form with those 7 letters. There will therefore be, in my results, on the one hand anagrams but also shorter words...

    The problem is that my algorithm returns true for words this* that do not contain the letters of s. What makes me even more perplexed is that with the same word, if I run the search on the entire dictionary several times in a row, it doesn’t always find the same false positives. That is, with the word "LETTRES" I sometimes have 46 positive results in the dictionary, sometimes 64, sometimes between the two... Of course the real "anagrams" always appear but the false positives seem to come and go randomly!

    The idea is that my algorithm compares words which can therefore be of different lengths this* with length ≤ s, which is my first line. For example, "BON" is – according to my definition – an anagram of "BONJOUR". The search therefore compares this->s2="BNO" and s.s2="BJO NO ORU". I traverse the two words by comparing the first letters, here equal -> I compare the second letters, different -> I increment my "cursor" on s.s2; to compare O and O, thus excluding the letter J. And I continue until the end, unless I find, for example, instead of J a P, which would mean that there is no O in s, and that this cannot be an "anagram" of s.

    It seems that the problem comes from my final return true; because apparently my false positives are composed of letters from s, and only of letters greater than the largest letter of s! For example "LUTTEUR-ELRTTUU" is a false positive of "LETTRES-EELRSTT" composed with two U’s greater than T, which was the last letter of EELRSTT...

    I can pinpoint the error, but I don’t see how to fix my problem, nor even how to treat it differently...

    —
    La confiance n'exclut pas le contrôle
    0
  4. Char Snipeur Posted messages 10112 Registration date   Status Contributor Last intervention   1 331
     
    OK, I understand better. I hadn’t understood your first explanation.
    Since your letters are ordered, it’s already easier.
    to make it clearer, it’s better to split your loop.
     bool stringD::isAnagram(stringD s) // is this* written with the letters of s? { if (size()>s.size()) return false; int j=0; for (unsigned i=0; i<size i="" while="" j="" if="" return="" false="" else="" true=""> 
    But you can also do this using a stack. (algorithmic writing, I’m not sure about the functions used) 
     bool stringD::isAnagram(stringD s) // is this* written with the letters of s? { if (size()>s.size()) return false; for(int i=0;i<s.size int="" pos="s.s2.find(s[i]);" if="" return="" false="" else="" s2.remove="" true=""> 
    -- 
    Best regards! (you must understand that I ALWAYS have the right) 
    Char Snipeur</s.size>
    </size></pre>
    0
  6. KX Posted messages 19031 Status Moderator 3 020
     
    Thank you, your first algorithm doesn’t work better, but starting from the idea of the second algorithm I managed to modify it and obtain the correct results, and more importantly with this method I have the impression that I can do without the preliminary sorting of the letters, which would save time/memory when loading the dictionary. 
    bool stringD::isAnagram(stringD s) { if (size()>s.size()) return false; for(unsigned i=0;i<size unsigned="" pos="s.s2.find(s2[i]);" if="" return="" false="" else="" s.s2.erase="" true="">Thanks again! 
    -- 
    Confidence does not exclude control</size>
    0