sort the 2 words and compare if both strings are same then both are anagrams

I will use extra space to solve this question, as sorting is a costly affair.

Regarding extra space, we only need to use memory for 256 character, not of O(n) if we know that string is made up of only ASCII characters. We can do more optimization on space, if we can put more restriction on our data type like if string will consist only of lower and upper character than I need space for only 50 characters......

From "http://www.careercup.com/question?id=18382"

solution was provided by "nirmalr" (modified slightly)

O(n) algorithm to check anagram :
+++++++++++++++++++++++++++++++++

variant of counting sort can be used here as the range is known.

algorithm :

input : string1, string2 (to be checked)

step 1: allocate one integer array c[26]
step 2: initialize elements of array c to zero

step 3 : for each character in string1
increment corresponding element in c by one (ex : for 'a', c[0]++)

step 4 : for each character in string2
decrement corresponding element in c by one (ex : for 'a', c[0]--)

step 5 : if "c" contains all zero then string1 & 2 are anagrams.

for optimization, step 3 and 4 can be merged together as they are independent activities.

nirmalr's algorithm assumes there is only alphabet characters. What about numbers and special characters? :)

bool isAnagram(string s1,string s2)
{
return s1.sort()==s2.sort();
}

i have a different approach using prime numbers.
all u need to do is maintain an array of first 26 prime numbers.

then for input string1 find its unique product value:
product_string1=1
for(i=0 to strlen(string1)) product_string1*=a[string[i]-'a']

if(strlen(string2)==strlen(string2)){
then find the product for string 2 in similar fashion
product_string2=1
for(i=0 to strlen(string2)) product_string2*=a[string[2]-'a']
if(product_string1==product_string2) string is anagram of string 1
}

Time complexity: Find the first 26 prime numbers, this will be done once only.
After that for every input it can said in o(n) time whether it is anagram or not where n is the string size. and space complexity is only int array of 26 to store first 26 prime numbers.