Anagrams.. A programming dilemma.

Hey Markus (or anyone else familiar with computer programming),

I am having some difficulty solving one of the problems on Codechef, and was wondering if you might be able to tell me if I've made an obvious mistake in my coding. Here is the problem statement:

---

In this problem, you are given two strings S1 and S2, your task is to determine whether one string is an anagram of the other. An anagram of a string is a string obtained by permuting the letters of a string. For example aaba and aaab are anagrams, while abcd and deba are not.

Input

The first line would consist of the number of test cases 'T'. This would be followed by 'T' lines consisting of two space separated strings. The strings would consist of only letters 'a'-'z'. Each string would consist of no more than 20 characters.

Output

You have to print "YES" if one string is an anagram of the other or "NO" otherwise.
Example

Input:
2
aaba aaab
abcd deba

Output:
YES
NO

---

My first step: I realize that each character has a specific value on the ASCII chart.. The letters a-z have the values 97-122. For this reason I decided that the best way to compare the two strings was by creating the following function and passing the two character arrays to it as arguments:



Lines 50 and 51 calculate the length in characters of string 'a', and string 'b' respectively

Lines 60-63 calculate the total of the ASCII values for string 'a', and lines 65-68 calculate the total of the ASCII values for string 'b'.

Finally, lines 70-73 determine whether the two strings are anagrams by comparing their ASCII totals and lengths. Then the word "YES" or "NO" is printed.

---

My program reproduces their sample input/output exactly, and it works with my tests as well.. However, when I submit my code I'm getting "Wrong Answer". So I'm wondering if maybe there is a test case that I am overlooking

Do you have to take into account lower case and upper case differences?

upper case A = 65, lower case a = 67

Thus ... zzz = 366 is both the same value and the same length as zaH - obviously THOSE are not anagrams.

Do you have to take into account other ASCII characters? What about Extended ASCII (up to 255).

What I suspect is that you may need to write a function that is recursive (calls itself until it is valid).

Hello,

you cannot just add the ascii values because the sum of ascii values for the string
'AC'
and
'BB'

would be the same and would result in a YES.

Right way is to build to Arrays with 256 element (from 0..255) and count the ascii values per char in one string and in the other string.
Then compare the 256 elements if all they are all equal.

Pseudo Code:
Define Array V1[256],V2[256] Integer
Set All V1 and V2 ZERO
for every char in S1 do V1[ascii(S1[i])]++
for every char in S2 do V2[ascii(S2[i])]++
Result = YES
for I=0 to 255 if V1[i]<>V2[i] then Result=NO

cu

Markus

Also:

This code example will only work with standard ascii input.
If you have korean, chinese or japanese languages installed it will fail since these chars are saved as wide string with an ascii value greater than 255.

In this case you will have to increase the compare arrays v1 and v2 to 16 bit with an element count of 65536 going from 0 to 65535 to compare.

Markus

dctim wrote:Do you have to take into account lower case and upper case differences?

upper case A = 65, lower case a = 67

Thus ... zzz = 366 is both the same value and the same length as zaH - obviously THOSE are not anagrams.

Do you have to take into account other ASCII characters? What about Extended ASCII (up to 255).

What I suspect is that you may need to write a function that is recursive (calls itself until it is valid).

Hey dctim, thanks for your reply. It doesn't look like I'd need to worry about uppercase letters for this problem, based on its statement.

I will have to see if I can come up with some code that'll account for strings that have different letters, but the same length and ASCII totals

Admin wrote:Hello,

you cannot just add the ascii values because the sum of ascii values for the string
'AC'
and
'BB'

would be the same and would result in a YES.

Right way is to build to Arrays with 256 element (from 0..255) and count the ascii values per char in one string and in the other string.
Then compare the 256 elements if all they are all equal.

Pseudo Code:
Define Array V1[256],V2[256] Integer
Set All V1 and V2 ZERO
for every char in S1 do V1[ascii(S1[i])]++
for every char in S2 do V2[ascii(S2[i])]++
Result = YES
for I=0 to 255 if V1[i]<>V2[i] then Result=NO

cu

Markus

Hey Markus,

Thanks for the input. I'm going to come back to this problem tomorrow morning and add the things you mention here. I don't know why I missed something as obvious as ac/bb. That's rather embarassing

Admin wrote:Hello,

you cannot just add the ascii values because the sum of ascii values for the string
'AC'
and
'BB'

would be the same and would result in a YES.

Right way is to build to Arrays with 256 element (from 0..255) and count the ascii values per char in one string and in the other string.
Then compare the 256 elements if all they are all equal.

Pseudo Code:
Define Array V1[256],V2[256] Integer
Set All V1 and V2 ZERO
for every char in S1 do V1[ascii(S1[i])]++
for every char in S2 do V2[ascii(S2[i])]++
Result = YES
for I=0 to 255 if V1[i]<>V2[i] then Result=NO

Hey Markus,

I couldn't quite understand this pseudocode last week, but I did understand what you were trying to illustrate with the 'BB' / 'AC' example.

I am a bit frustrated this morning.. I spent some time coming up with a function to compare each string character by character, and came up with this:



This function is called from bool anagram() as follows (see lines 77-85):



I tested this new code out with the example you gave me, and it returns "NO", just as it should. However, when I submit to CodeChef they still tell me that I am wrong. I'm not sure what else to do with this one right now, I feel like I've tried everything that I know

Aaron,

my pseudo code function is just a copy of what a human eye would do if looking at this two strings. And this is by the way always the best to go from problem to solution.

Don't care about the length of the two strings. Just count in both strings the amount of 'A' 'B' 'C' into two result arrays. Then compare the two arrays if the amount of 'A' 'B' 'C' counted is in both string always the same.

Strings with different length will automatically have not the same result in at least one of the chars elements. This is how you keep the code short.

I do not program in C at all, but here is the important part in hopefully good C, lol.
I did use your var names, all you need to do is define an array of int length 255 with the names strcount and str2count. These arrays will hold the value for every of the 255 ascii counted. So the string AC will result counted a 1 in strcount[65] and strcount[67] since ascii(a)=65 and ascii(c)=67. The String BB will result in str2count[66]=2,str2count[65] will be zero. At the end you compare the two count arrays and AC and BB will result in an ANA=FALSE !

for (int i = 0; i< strlen(str); i++) { strcount[ str[i] ] ++ }
for (int i = 0; i< strlen(str2); i++) { str2count[ str2[i] ] ++ }
Ana= true;
for (int i = 0; 255; i++) { if strcount[i]<>str2count[i] then Ana=false }

hopefully this helps

Markus