Anagram Function - Reapeated letters Problem

[gretty]

Hello

I have made a function that determines whether 2 words are an anagram or not.
My Problem is: that if the word contains 2 or more of the same letters(eg hello, arrest, gall) the function doesn't work even when the 2 words input are an anagram,

If i input "ate" & "eat" my function returns true - so it works
But if I input "mello" & "ollem" - I know these are not words but it should still return true, but it doesn't because the repeated 'l' confuses the function...I think? :P

function:

bool areAnagrams (string s1, string s2)
// pre : s1 and s2 are lower case strings
// post : returns true if s1 and s1 are anagrams
//        and otherwise false
{
	int count = 0;

	if (s1.length() != s2.length()) {
		return false;
	}

	// check if all the letters that occur in s1 are
	// present in s2 also.

	for (int i=0; i<(int)s1.length(); i++) {
		for (int j=0; j<(int)s1.length(); j++) {
			if (s1[i]==s2[j])  count++;
		}
	}

	if (count==(int)s1.length())
	{
		return true;
	}
	else return false;

}

Whole code:

#include <iostream>
using namespace std;

bool areAnagrams(string s1, string s2);
int main()
{
	string word1, word2;
	cout << "Enter pairs of words - terminate with control-z" << endl;

	while (cin >> word1 >> word2) // complete this
	{
		if (areAnagrams (word1, word2))
			cout << word1 << " and " << word2 << " are anagrams " << endl;
		else
			cout << word1 << " and " << word2 << " are not anagrams " << endl;
	}
	system("pause");
	return 0;
}
bool areAnagrams (string s1, string s2)
// pre : s1 and s2 are lower case strings
// post : returns true if s1 and s1 are anagrams
//        and otherwise false
{
	int count = 0;

	if (s1.length() != s2.length()) {
		return false;
	}

	// check if all the letters that occur in s1 are
	// present in s2 also.

	for (int i=0; i<(int)s1.length(); i++) {
		for (int j=0; j<(int)s1.length(); j++) {
			if (s1[i]==s2[j])  count++;
		}
	}

	if (count==(int)s1.length())
	{
		return true;
	}
	else return false;

}

[iamthwee]

Letter frequency counter?

[gretty]

Letter frequency counter?

I am not quite what you mean? :)

[iamthwee]

Just do a match on the letters

for example hello has:

1 h
1 e
1 o
2 l

Therefore any word which has the same will be an anagram.

[Sky Diploma]

Hey a better way would be to delete the particular letter in the string after you encounter it.

using the string::erase() function.

In the end you will have to just chek if the string is empty(); and then you have a anagram.

[mrnutty]

Let the string class do all the work. use stringVariable.find() function.

Here is an example :

bool isAnagram(string& str1, string& str2)
{
	//check for length equality
	if(str1.length() != str2.length()) 
		return false;
	
	if(!str1) 
		return false;

	//check for string equality
	if(str1 == str2) return true;

	for(int i = 0; i < str1.length(); i++)
	{
		//search both ways

		if(str1.find(str2[i]) == string::npos)
			return false;
		if(str2.find(str1[i]) == string::npos) 
			return false;
	}

	return true;
}

[mrnutty]

Correction : Its
if(!str1[0])
return false;

and not
if(!str1)
return false;

[gretty]

Let the string class do all the work. use stringVariable.find() function.

Here is an example :

bool isAnagram(string& str1, string& str2)
{
	//check for length equality
	if(str1.length() != str2.length()) 
		return false;
	
	if(!str1) 
		return false;

	//check for string equality
	if(str1 == str2) return true;

	for(int i = 0; i < str1.length(); i++)
	{
		//search both ways

		if(str1.find(str2[i]) == string::npos)
			return false;
		if(str2.find(str1[i]) == string::npos) 
			return false;
	}

	return true;
}

Thanks for the example, I never knew about the string find function & that npos aswell :)

One question: what does this line do? Am I right in saying that it checks that s1 is larger than 0 characters?

if(!s1[0])
return false; // is this checking if string one if greater than 0 characters?

[mrnutty]

It checks to see if there is a string to check for anagram.

Since technically this check below :

if(str1.length() != str2.length())
return false;

could pass if both string is null;

So it checks to see if they are null;

Also I only need to check 1 string for null, since it will already
be determined that they both have the same length.

[zalezog]

I didn't want to poke but firstPerson's method doesn't take into account the frequency of characters, so for inputs
like s1 = roorsseett
s2 = sosretetet
returns true.
letter s1 s2
r 2 1
o 2 1
.
.
or inputs like
s1 = rorre
s2 = oroee
returns true.

Another method would be to sort the strings(may be using quicksort) and then check character by character, if both the strings are anagrams, then after sorting both s1[index] must be equal to s2[index] else strings are not anagrams.

Another thing to take into account are whether there are spaces, and to strip them before sorting.While capitalized characters should be converted into lower case before sorting.

You'll also have to decide whether to take into characters other than alphanumeric ones. Consider
s1 = O, Draconian Devil
s2 = Leonardo Da Vinci
you have got to remove that comma in any method you follow as well as the spaces

[Sky Diploma]

Well, THis was my approach to the code.

for (int a=0; a<str1.size();a++)
{
size_t  val=str2.find(str1[a]);
 if(val==string::npos)
  return false;
  else 
   str2.erase(val,val);
}
return str2.empty();

THough i dint try it out, hope it works fine.

[Sky Diploma]

A Small change would be .....

str2.erase(val,val);

to

str2.erase(val,1);

Thanks to tux4life.

[tux4life]

And....Another approach (maybe not the most efficient one):

bool isAnagram(string str1, string str2)
{
  sort(str1.begin(), str1.end());
  sort(str2.begin(), str2.end());
  if(str1 == str2) return true;
	
  return false;
}

(You'll need to include the algorithm header file, you can do this by adding the following include directive to your program: #include <algorithm> )

[mrnutty]

.