C++ program to test for anagrams!!


This question was asked to me in final round of MICROSOFT… That time I did it by brute force (everyone does it the same way, when it’s their first time .. )

But, now I have come up with a different approach. This idea should have come to me a day earlier and I would have been sitting in Microsoft…

The program would be posted by me later, when I get internet on my own laptop… Till then you can see the algorithm…

Take an integer variable and set it to x=0

Now, letter by letter add the letter’s ascii value to the integer and finally compare the two integers…

The time complexity for this algo is O(n), while for brute force it turns out to be O(n2)… Hope you understood..!!

Ok, as said by Mr. AAA, there would be a problem in this solution given by me. So, here I present another solution:

Firstly, create two 26 lettered hash tables for all the english alphabets (or for whatever is the range of your letters used). Initialize these hash tables to values 0. Now, scan the words and increment the respected letters by 1 each time that letter comes. For eg., if the word is “foo”, increment ‘f’ to 1 and ‘o’ to 2. Now, compare the two hash tables, and you will get the answer…

Thus, this algorithm also works in O(n).

Advertisements
Explore posts in the same categories: C++

4 Comments on “C++ program to test for anagrams!!”

  1. AAA Says:

    The above algorithm will fall down if the inputs are ‘ac’ and ‘bb’ as the sum for the two ascii values is same. Try for something else…

  2. techmyway Says:

    Hope you understood the updated algo given by me. If any problem persists, please write again..


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: