bool function problem - always returns true ?

Question

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cstdio>

using namespace std;

static bool isanagram(string a, string b);

int main(void)
{
    int i,n,j,s;
    cin >> n;
    string a, b;
    cin >> a >> b;
    if(!isanagram(a,b)) cout << "False" << endl;
    else cout << "True" << endl;
    return 0;


}

static bool isanagram(string a, string b)
{
    int i, j, size, s=0;
    size = a.size();
    bool k;
    for(i=0;i<size;i++)
    {
        k=false;
        for(j=0;j<size;j++)
        {
            if(a[i] == b[j]) { k = true; break; }
        }
        if(k==true) s+=1;
    }
    cout << a[2] << b[2] << endl;
    if(s == size) return true;
    else return false;

}

I don't know where exactly is the problem so i just pasted the whole code.

It should be a simple program capable for finding if two strings are anagrams, but it's not working and i don't know why. I used pointers in the program so thought the might be the problem and removed them, i removed other things additionally but still it's not working. If you can give it a look-see and tell me some idea where i might've gone wrong with my code ?

Thank you in advance.

Answer 1

It's not always return true:

Here's my input:

0
sdf 
fda

Here's output I got:

fa 
False

Regarding your task: if performance is not an issue for you task, just sort 2 strings (using std::sort) and compare results.

Regarding your style:

• use string::length() instead of size() -- it's more idiomatic
• instead of if(s == size) return true; else return false; consider return s == size
• pass your strings by const reference, not by value
• consider declaring variables as close to point of their usage as possible (but not closely) and initialize them when declaring (i, j, k, size all fit this hint)

Answer 2

The logic for your isanagram function is fatally flawed - it will never work correctly, even if you manage to fix the bugs in it.

You need to make sure that you have a correct algorithm before you start coding. One simple algorithm might be:

• sort a
• sort b
• isanagram = (a == b)

Answer 3

You seem to be checking if the set of characters of string a appear in the first a.size characters of string b.

You need to sort both strings and compare for exact match.

Answer 4

There are essentially two ways of checking for anagrams:

1. Sort both strings and see if they match. If they are anagrams, they will both have the same letters and a sort would order them into the same sequence.

2. Count the frequency of each char in each string. If they are anagrams, the frequency counts for each char will be the same for both strings.

Answer 5

I see some problems with your code. Basically the algorithm is wrong. It will match characters within a.size(). It takes no account for duplicates (in either a or b).

Essentially, you should sort the strings and then compare for equality.

If you can't sort, at least remove the b characters from the comparison, eliminate the k variable.

Answer 6

Your approach is fine but it has a small flaw. You ensuring that every char from string a is present in string. So if a = "aab" and b = "abc", your approach will flag them as anagram. You also need to take the count of char in account.

The definition of anagram is:

An anagram is a type of word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once;

Easiest way as many have suggested is to ensure that the strings are of the same length . If they are, sort the two string and check for equality.

If you want to patch your approach, you can make the char in string b NULL after it has been matched with a char in string a.

Something like:

if(a[i] == b[j]) { b[j] = 0; k = true; break; }

in place of your:

if(a[i] == b[j]) { k = true; break; }

This way once a char of b has been matched it cannot participate again.

Answer 7

First things first: don't declare the method static. It's a confusing keyword at the best of times given all the roles it can fulfill... so reserve for times when you really have to (method or attribute of a class that is not tied to any instance for example).

Regarding the algorithm: you're nearly there, but presence only is not sufficient, you need to take the number of characters in account too.

Let's do it simply:

bool anagram(std::string const& lhs, std::string const& rhs)
{
  if (lhs.size() != rhs.size()) return false; // does not cost much...

  std::vector<int> count(256, 0); // count of characters
  for (size_t i = 0, max = lhs.size(); i != max; ++i)
  {
    ++count[lhs[i]];
    --count[rhs[i]];
  }

  for (size_t i = 0, max = count.size(); i != max; ++i)
    if (count[i] != 0) return false;

  return true;
} // anagram

Let's see it at work: anagram("abc","cab")

1. Initialization: count = [0, 0, ...., 0]
2. First loop i == 0 > ['a': 1, 'c': -1]
3. First loop i == 1 > ['a': 0, 'b': 1, 'c': -1]
4. First loop i == 2 > ['a': 0, 'b': 0, 'c': 0 ]

And the second loop will pass without any problem.

Variants include maintaining 2 counts arrays (one for each strings) and then comparing them. It's slightly less efficient... does not really matter though.

int main(int argc, char* argv[])
{
  if (argc != 3) std::cout << "Usage: Program Word1 Word2" << std::endl;
  else std::cout << argv[1] << " and " << argv[2] << " are "
                 << (anagram(argv[1], argv[2]) ? "" : "not ")
                 << "anagrams" << std::endl;
}