Description: 2 strings are said to be anagrams if they contain the same letters, however the ordering of characters may be different. Given 2 strings, we have to check if they are anagrams.

 
If video does not load, Click here
 
Example:
1)      “pqrs”
2)      “sqrp”               

Here, 1 and 2 are anagrams.

Algorithm:

This problem can be solved using 2 approaches-

1) Using sorting(O(nlgn))-no extra space

2) Using auxiliary space (O(n))

 

1)Using sorting

-Sort both strings using merge-sort(nlogn).

-Match each element of both sorted strings.

    

 If match, ANAGRAM

Eg:”pqsr” à“pqrs” (after sorting)

      “sqrp” à“pqrs” (after sorting)

 

2) Using auxiliary space

 

1.  Create arrays ‘count1’ and ‘count2’ and initialize all elements to 0.

2.  Scan through each string updating ‘count1’ / ‘count2’ corresponding to each character scanned.

In string 1, count1[string1[i]]++;

In string 2, count2[string2[i]]++;

 

The arrays ‘count1’ and ‘count2 ‘ store the number of occurences of each character in the 1st and 2nd strings respectively.

3. Compare count1 and count2. If for every character the values are same, ANAGRAM

Eg: “pqsr”                                              “sqrp”

      count1[‘p’]=1;                           count2[‘p’]=1;

      count1[‘q’]=1;                           count2[‘q’]=1;

      count1[‘r’]=1;                            count2[‘r’]=1;

      count1[‘s’]=1;                            count2[‘s’]=1;

Implementation in C:
 
# define NO_OF_CHARS 256
 
/* Function to check whether two strings are anagram of each other */
 
int Anagram(char *str1, char *str2)
{
    /* Create two count arrays and initialize all values as 0 */
    int count1[NO_OF_CHARS] = {0};
    int count2[NO_OF_CHARS] = {0};
    int i;
 
    /* For each character in input strings, increment count in the corresponding    count array */
    for (i = 0; str1[i] && str2[i];  i++)
    {
        count1[str1[i]]++;
        count2[str2[i]]++;
    }
 
    /* If both strings are of different length. Removing this condition
     will make the program fail for strings like "aaca" and "aca" */
   
 if (str1[i] || str2[i])
      return 0;
 
    /* Compare count arrays */
    for (i = 0; i < NO_OF_CHARS; i++)
        if (count1[i] != count2[i])
            return 0;
 
    return 1;
}
Go to top