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.

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