Fast anagram determination
/****************************************************************************** * This function is a code snippet. It can be freely used and distributed. * Author: irfan.hamid@gmail.com * * This function takes two ASCII strings in C syntax (null-terminated * character arrays) and determines whether they are anagrams or not. * * Implementation notes: * The function contains a histogram that stores the frequency of each * character it encounters in the first string. For each character of the * second string, it decrements the corresponding entry in the histogram. If * before every decrement, the value of the histogram bucket reaches zero, * then the two strings are not anagrams, as there is some character that has * more occurrences in the second string than in the first string. * * If either of the two strings contains a non-alphabetic character, the * anagram property is considered to be violated. * * Remarks: * It is an efficient implementation because: * o It is in-place, the original strings are not copied, no alloc or copy * o Does not clobber the original strings * o It is a linear time implementation * * Returns: * True if the strings are anagrams, false otherwise. ******************************************************************************/ bool is_anagram (char w1[], char w2[]) { unsigned int i, sz; /* The histogram */ int freqtbl[26]; /* Sanity check */ if ((sz = strlen(w1)) != strlen(w2)) return false; /* Initialize the histogram */ bzero(freqtbl, 26*sizeof(int)); /* Read the first string, incrementing the corresponding histogram entry */ for (i = 0; i < sz; i++) { if (w1[i] >= 'A' && w1[i] <= 'Z') freqtbl[w1[i]-'A']++; else if (w1[i] >= 'a' && w1[i] <= 'z') freqtbl[w1[i]-'a']++; else return false; } /* Read the second string, decrementing the corresponding histogram entry */ for (i = 0; i < sz; i++) { if (w2[i] >= 'A' && w2[i] <= 'Z') { if (freqtbl[w2[i]-'A'] == 0) return false; freqtbl[w2[i]-'A']--; } else if (w2[i] >= 'a' && w2[i] <= 'z') { if (freqtbl[w2[i]-'a'] == 0) return false; freqtbl[w2[i]-'a']--; } else { return false; } } return true; }