Anagrams?????

Go down

Anagrams?????

Post  Admin on Tue Aug 12, 2008 8:49 am

You have been given 2 strings str1 and str2. Find whether the strings are anagrams of each other. What will be the test cases??

Admin
Admin

Posts : 39
Join date : 2008-08-03

View user profile http://computerclub09mnnit.forumotion.net

Back to top Go down

Re: Anagrams?????

Post  sweetesh singh on Tue Aug 12, 2008 9:14 am

xor the two strings if output is 0 then print yes else print no.

sweetesh singh

Posts : 8
Join date : 2008-08-12

View user profile

Back to top Go down

Re: Anagrams?????

Post  sweetesh singh on Tue Aug 12, 2008 10:59 am

if two strings are permut of each other then above algo will definately output yes but reverse is not true
1)str1="aaaa",str2="bbbbbb"
2)str1="aa",str2="\0";
and similar strings where we get even number of same chars.
so i think min complexity to sol this for handling all case shud be nlogn (sort it optimally and comp char by char)

sweetesh singh

Posts : 8
Join date : 2008-08-12

View user profile

Back to top Go down

Re: Anagrams?????

Post  shivang on Tue Aug 12, 2008 3:01 pm

This Algorithm can be applied to any no of stings gven and to compute the set of the anagrams in it......

For each word in the list, form a new word by sorting the letters in
that word. Each set of anagrams would have the same
sorted-letter-word.

You could then sort the list of words alphabetically by the sorted-letter-words.

It's order N * log N.
avatar
shivang

Posts : 22
Join date : 2008-08-11
Age : 29
Location : Tondon 174

View user profile

Back to top Go down

Re: Anagrams?????

Post  ankurgutpa on Wed Aug 13, 2008 2:50 am

int a[256]={0};
if strlen(s1)=strlen(s2){
while(*s1 && a[*s1++]++ && a[*s2++]--)
;
i=-1;
while(++i<256 && a[i]==0)
;
i==256?"anagram":"not an anagram"
}
else "not an angram

This will work for all test cases in O(n) cheers
avatar
ankurgutpa

Posts : 44
Join date : 2008-08-10
Age : 31
Location : Tandon 72

View user profile

Back to top Go down

Re: Anagrams?????

Post  Sponsored content


Sponsored content


Back to top Go down

Back to top


 
Permissions in this forum:
You cannot reply to topics in this forum