Tuesday, July 10, 2012

Write a program to find if two strings are anagrams

Anagram - Wikipedia
An anagram is a type of word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once; for example orchestra can be rearranged into carthorse.

The approach:-
1. Check string lengths.
2. Initialize a frequency table to keep count of characters seen.
3. Scan the first string and increment the frequency table.
4. Scan the second string and decrement the frequency table.
5. Check if the frequency table has count more than zero in any of the locations. If so, not an anagram. Else, anagram.

C++ program to find if two strings are anagrams

#include <iostream>
#include <cstring>

using namespace std;

#define MAX_ASCII 127

int main()
{
    char s1[] = "orchestra";
    char s2[] = "carthorse";

    if ( strlen(s1) != strlen(s2) )
    {
        cout << "Not anagram" << endl;
        return 0;
    }

    int freq[MAX_ASCII + 1];

    for ( int i = 0; i < MAX_ASCII + 1; i++ )
        freq[i] = 0;

    char* ptr1 = s1;
    while ( *ptr1 != '\0' ) {
        char c = tolower(*ptr1);
        freq[(int)c]++;
        ptr1++;
    }

    char *ptr2 = s2;
    while ( *ptr2 != '\0' ) {
        char c = (char)tolower(*ptr2);
        freq[(int)c]--;
        ptr2++;
    }

    for ( int i = 0; i < MAX_ASCII + 1; i++ )
        if ( freq[i] > 0 )
        {
            cout << "Not anagram" << endl;
            return 0;
        }
        else
        {
            continue;
        }

    cout << "Anagram" << endl;
    return 0;
}


Output:-
Anagram

1 comment :

  1. Sort and see if the strings match. If so, they are anagrams, if not, they are not. Quicksort can be done in O(nlogn).

    ReplyDelete

Contact Form

Name

Email *

Message *

Back to Top