DaniWeb Forum Index > Software Development > C++

Anagram Function - Reapeated letters Problem

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Apr 2009

Posts: 150

Reputation: gretty is an unknown quantity at this point

Solved Threads: 7

gretty

Offline

Junior Poster

Anagram Function - Reapeated letters Problem

Aug 14th, 2009

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?

function:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
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;
 
}
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:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#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;
 
}
#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;

}

Last edited by gretty; Aug 14th, 2009 at 4:03 am.

•

Join Date: Aug 2005

Posts: 5,273

Reputation: iamthwee is a splendid one to behold

Solved Threads: 378

iamthwee

Offline

Posting Expert

Re: Anagram Function - Reapeated letters Problem

Aug 14th, 2009

Letter frequency counter?

*Voted best profile in the world*

•

Join Date: Apr 2009

Posts: 150

Reputation: gretty is an unknown quantity at this point

Solved Threads: 7

gretty

Offline

Junior Poster

Re: Anagram Function - Reapeated letters Problem

Aug 14th, 2009

•

Originally Posted by iamthwee

Letter frequency counter?

I am not quite what you mean?

•

Join Date: Aug 2005

Posts: 5,273

Reputation: iamthwee is a splendid one to behold

Solved Threads: 378

iamthwee

Offline

Posting Expert

Re: Anagram Function - Reapeated letters Problem

Aug 14th, 2009

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.

*Voted best profile in the world*

•

Join Date: Mar 2008

Posts: 678

Reputation: Sky Diploma is a splendid one to behold

Solved Threads: 101

Sky Diploma Sky Diploma is offline

Offline

Practically a Master Poster

Re: Anagram Function - Reapeated letters Problem

Aug 14th, 2009

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.

1. Please Mark Your Thread as Solved After Getting Your Answers.
2. Please Use CODE TAGS .

•

Join Date: Dec 2008

Posts: 1,435

Reputation: firstPerson is just really nice

Solved Threads: 186

firstPerson firstPerson is offline

Offline

Nearly a Posting Virtuoso

Re: Anagram Function - Reapeated letters Problem

Aug 14th, 2009

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

Here is an example :

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
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;
}
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;
}

Help with Code Tags

(Toggle Plain Text)

1) Prove that the area of a circle is pi*r^2, where "r" is the radius of the circle.
2) Problem 2[b]solved by : jonsca

•

Join Date: Dec 2008

Posts: 1,435

Reputation: firstPerson is just really nice

Solved Threads: 186

firstPerson firstPerson is offline

Offline

Nearly a Posting Virtuoso

Re: Anagram Function - Reapeated letters Problem

Aug 14th, 2009

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

and not
if(!str1)
return false;

Help with Code Tags

(Toggle Plain Text)

1) Prove that the area of a circle is pi*r^2, where "r" is the radius of the circle.
2) Problem 2[b]solved by : jonsca

•

Join Date: Apr 2009

Posts: 150

Reputation: gretty is an unknown quantity at this point

Solved Threads: 7

gretty

Offline

Junior Poster

Re: Anagram Function - Reapeated letters Problem

Aug 15th, 2009

•

Originally Posted by firstPerson

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

Here is an example :
Help with Code Tags

C++ Syntax (Toggle Plain Text)
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;
}
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?

•

Join Date: Dec 2008

Posts: 1,435

Reputation: firstPerson is just really nice

Solved Threads: 186

firstPerson firstPerson is offline

Offline

Nearly a Posting Virtuoso

Re: Anagram Function - Reapeated letters Problem

Aug 15th, 2009

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.

Help with Code Tags

(Toggle Plain Text)

1) Prove that the area of a circle is pi*r^2, where "r" is the radius of the circle.
2) Problem 2[b]solved by : jonsca

•

Join Date: Oct 2008

Posts: 45

Reputation: zalezog is an unknown quantity at this point

Solved Threads: 11

zalezog

Offline

Light Poster

Re: Anagram Function - Reapeated letters Problem

#10

Aug 15th, 2009

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

Last edited by zalezog; Aug 15th, 2009 at 8:49 am.