1  
   2  /******************************************************************************
   3   * This function is a code snippet. It can be freely used and distributed.
   4   * Author: irfan[dot]hamid[at]gmail[at]com
   5   *
   6   * This function takes two ASCII strings in C syntax (null-terminated
   7   * character arrays) and determines whether they are anagrams or not.
   8   *
   9   * Implementation notes:
  10   * The function contains a histogram that stores the frequency of each 
  11   * character it encounters in the first string. For each character of the 
  12   * second string, it decrements the corresponding entry in the histogram. If 
  13   * before every decrement, the value of the histogram bucket reaches zero, 
  14   * then the two strings are not anagrams, as there is some character that has
  15   * more occurrences in the second string than in the first string.
  16   *
  17   * If either of the two strings contains a non-alphabetic character, the
  18   * anagram property is considered to be violated.
  19   *
  20   * Remarks:
  21   * It is an efficient implementation because:
  22   *   o It is in-place, the original strings are not copied, no alloc or copy
  23   *   o Does not clobber the original strings
  24   *   o It is a linear time implementation
  25   *
  26   * Returns:
  27   * True if the strings are anagrams, false otherwise.
  28  ******************************************************************************/
  29  
  30  bool is_anagram (char w1[], char w2[])
  31  {
  32  	unsigned int i, sz;
  33  
  34  	/* The histogram */
  35  	int freqtbl[26];
  36  
  37  	/* Sanity check */
  38  	if ((sz = strlen(w1)) != strlen(w2))
  39  		return false;
  40  
  41  	/* Initialize the histogram */
  42  	bzero(freqtbl, 26*sizeof(int));
  43  
  44  	/* Read the first string, incrementing the corresponding histogram entry */
  45  	for (i = 0; i < sz; i++) {
  46  		if (w1[i] >= 'A' && w1[i] <= 'Z')
  47  			freqtbl[w1[i]-'A']++;
  48  		else if (w1[i] >= 'a' && w1[i] <= 'z')
  49  			freqtbl[w1[i]-'a']++;
  50  		else
  51  			return false;
  52  	}
  53  
  54  	/* Read the second string, decrementing the corresponding histogram entry */
  55  	for (i = 0; i < sz; i++) {
  56  		if (w2[i] >= 'A' && w2[i] <= 'Z') {
  57  			if (freqtbl[w2[i]-'A'] == 0)
  58  				return false;
  59  			freqtbl[w2[i]-'A']--;
  60  		} else if (w2[i] >= 'a' && w2[i] <= 'z') {
  61  			if (freqtbl[w2[i]-'a'] == 0)
  62  				return false;
  63  			freqtbl[w2[i]-'a']--;
  64  		} else {
  65  			return false;
  66  		}
  67  	}
  68  
  69  	return true;
  70  }