Detect Anagram in a String

 

Question

Detect whether a string is anagram of the another string. The normal brute force way would be like this,

Answer

bool detect_anagram(char* src, char* anagram)

{

    int isrc=0, iana=0;

    while(*src != '\0') {

        char* iter = anagram;

        while(*iter != '\0' && *src != ' ') {

            if(*src == *iter) {

                iana++;

                break;

            }

            iter++;

        }

        if(*src != ' ')

            isrc++;

        src++;

    }

    if(iana == isrc)

        return true;

    else

        return false;

}

void main()

{

    char *src=strdup("eleven plus two");

    char *a = strdup("so plew veluent");

    bool st = detect_anagram(src, a);

}

Important points

• The above approach ignores all space character ‘ ‘ and checks for occurrence of a character in the anagram string. If the number of equal characters is equal to the number of characters in source string, then the string is an anagram!!..
• iter is the iterator for the anagram string
• We iterate until we find a matching character in the iter. If we find one, we just increment the count and break.
• iana will be equal to isrc only when characters in source string = anagram string. This is the invariant we need to use to prove the correctness of the above code

Alternate approaches:

• sort both the strings and check whether both are equal!!
• Take count of characters in original string first and then start decrementing the count when seeing the same in the anagram string. If the count becomes zero for all the recorded character entries, then the string is an anagram. This approach is little bit faster than our above O(N2) approach.