Back to: C Tutorials For Beginners and Professionals
How to Check if 2 Strings are Anagram in C Language
In this article, I will discuss How to Check if 2 Strings are Anagram in C Language with Examples. Please read our previous article discussing Finding Duplicates in a String using Bitwise Operations in C Language with Examples. Anagrams are words or phrases containing the same number of characters in any order. At the end of this article, you will understand the following five approaches to Check if 2 Strings are Anagram:
- Check if 2 Strings are Anagram in C using the Character Count Method.
- Check if 2 Strings are Anagram in C Using the Hash Table Method.
- Check if 2 Strings are Anagram in C Using the Bit Manipulation Method.
- Check if 2 Strings are Anagram in C Using the Prime Number Multiplication Method.
- Check if 2 Strings are Anagram in C using the Sorting and Comparing Method.
Checking if 2 Strings are Anagram in C Language:
Now, we will see how to check whether two strings are anagrams. First, let’s understand what is meant by anagram. An anagram is the two sets of strings that are formed using the same set of alphabets. Please observe the following two strings.
Here, we have a string, i.e., listen, and the same alphabet is used in another string, i.e., silent. So, these are anagrams. Now, we have to check whether two strings are anagrams or not. So, the first and foremost thing is to check whether two strings are of equal size. If they are different sizes, they cannot be anagrams. The following are the five approaches to check whether two strings are anagrams.
- Character Count Method: This is the most straightforward approach. It involves counting the occurrences of each character in both strings and then comparing these counts.
- Sorting and Comparing Method: Another approach is to sort both strings and then compare them. If they are anagrams, the sorted strings will be identical.
- Hash Table Method: Use a hash table to count character occurrences. This is a variation of the character count method but can be more efficient with larger character sets or when dealing with Unicode characters.
- Bit Manipulation Method: This method is applicable only if the string contains alphabetic characters and is case-insensitive. It uses bitwise operations to track character occurrences.
- Prime Number Multiplication Method: Assign a unique prime number to each character and multiply these numbers for each character in the strings. Due to the fundamental theorem of arithmetic, two anagrams will have the same product.
Approach 1: Check if 2 Strings are Anagram in C Example using the Character Count Method
Checking if two strings are anagrams in C using the character count method involves comparing the frequency of each character in both strings. The approach is quite straightforward and efficient for most cases. Here’s an example of how you can implement this:
- Character Count Arrays: Create two arrays to count the occurrences of each character for the two strings. Since there are 256 ASCII characters, each array should be of size 256.
- Count Characters: Iterate over each string and increment the count of each character in the corresponding array.
- Compare Counts: Compare the two character count arrays. If they match for every character, the strings are anagrams of each other.
Here’s a C program implementing the above logic:
#include <stdio.h> #include <string.h> #include <stdbool.h> #define MAX_CHARS 256 bool areAnagrams(const char *str1, const char *str2) { int count1[MAX_CHARS] = {0}; int count2[MAX_CHARS] = {0}; int i; // Count characters in both strings for (i = 0; str1[i] && str2[i]; i++) { count1[str1[i]]++; count2[str2[i]]++; } // If both strings are of different lengths, they are not anagrams if (str1[i] || str2[i]) return false; // Compare character counts of both strings for (i = 0; i < MAX_CHARS; i++) if (count1[i] != count2[i]) return false; return true; } int main() { char str1[] = "triangle"; char str2[] = "integral"; if (areAnagrams(str1, str2)) { printf("'%s' and '%s' are anagrams.\n", str1, str2); } else { printf("'%s' and '%s' are not anagrams.\n", str1, str2); } return 0; }
In this program, areAnagrams checks if “triangle” and “integral” are anagrams. It counts the frequency of each character in both strings using arrays count1 and count2. If the frequency of every character in count1 matches its corresponding frequency in count2, and both strings are the same length, the function returns true, indicating the strings are anagrams.
This method is case-sensitive and considers all ASCII characters. You might need to adjust the program if you require case-insensitivity or want to consider only alphabetic characters.
- Pros: Simple and efficient for ASCII characters.
- Cons: Not very efficient for large character sets (like Unicode).
Approach 2: Check if 2 Strings are Anagram in C Example Using Hash Table Method
To check if two strings are anagrams using a hash table in C, you can follow these steps:
- Create a Hash Table: Initialize an array of integers with a size equal to the number of possible characters (e.g., 256 for extended ASCII characters). This array will serve as your hash table, with each index representing a character and the value at each index representing the count of that character.
- Process the First String: Iterate through the characters of the first string. For each character, increment the count in the corresponding index of the hash table.
- Process the Second String: Iterate through the characters of the second string. For each character, decrement the count in the corresponding index of the hash table.
- Check the Hash Table: After processing both strings, iterate through the hash table. If all counts are zero, the strings are anagrams of each other. If any count is not zero, they are not anagrams.
Here’s a sample C code to illustrate this:
#include <stdio.h> #include <string.h> #include <stdbool.h> #define CHAR_RANGE 256 // Assuming extended ASCII bool areAnagrams(char *str1, char *str2) { int count[CHAR_RANGE] = {0}; int i; // Process first string for (i = 0; str1[i] && str2[i]; i++) { count[(unsigned char)str1[i]]++; count[(unsigned char)str2[i]]--; } // If both strings are of different length if (str1[i] || str2[i]) return false; // Check hash table counts for (i = 0; i < CHAR_RANGE; i++) { if (count[i]) return false; } return true; } int main() { char str1[] = "listen"; char str2[] = "silent"; if (areAnagrams(str1, str2)) printf("'%s' and '%s' are anagrams.\n", str1, str2); else printf("'%s' and '%s' are not anagrams.\n", str1, str2); return 0; }
Using the hash table method, this code will check if the two strings str1 and str2 are anagrams of each other. Remember to adjust the CHAR_RANGE constant if you’re working with a character set with a different range than extended ASCII.
- Pros: Efficient for large character sets and scalable.
- Cons: Requires additional data structure complexity.
Approach 3: Check if 2 Strings are Anagram in C Example Using Bit Manipulation Method
Checking if two strings are anagrams using bit manipulation is unconventional and less straightforward than other methods like counting or sorting. This approach can be particularly challenging because bit manipulation typically works best with bitwise operations, like XOR, AND, OR, etc., and anagram checking involves counting or comparing character occurrences, which is not directly bitwise.
However, if we assume that the strings only contain lowercase alphabetic characters (‘a’ to ‘z’), we could use a bit vector (a long integer) to represent the presence or absence of each letter. The idea would be to set a bit for each letter that appears in each string and then compare these bit vectors. This method won’t work if characters are repeated or if there are characters outside of ‘a’ to ‘z’.
- Pros: Very efficient in terms of space and time for limited character sets (e.g., ‘a’ to ‘z’).
- Cons: Limited to certain types of character sets. Not suitable for unicode or case-sensitive comparisons.
Here’s an example in C using this limited approach:
#include <stdio.h> #include <string.h> // Function to calculate the bit vector for a string unsigned long long getBitVector(char *str) { unsigned long long bitVector = 0; for (int i = 0; str[i] != '\0'; i++) { // Set the bit corresponding to the character bitVector |= 1 << (str[i] - 'a'); } return bitVector; } // Check if two strings are anagrams using bit manipulation int areAnagrams(char *str1, char *str2) { // Get the bit vectors for both strings unsigned long long bitVector1 = getBitVector(str1); unsigned long long bitVector2 = getBitVector(str2); // Compare the bit vectors return bitVector1 == bitVector2; } int main() { char str1[] = "triangle"; char str2[] = "integral"; if (areAnagrams(str1, str2)) { printf("'%s' and '%s' are anagrams.\n", str1, str2); } else { printf("'%s' and '%s' are not anagrams.\n", str1, str2); } return 0; }
In this program:
- getBitVector function creates a bit vector for a given string. It sets a bit for each character present in the string.
- areAnagrams function compares the bit vectors of the two strings.
- The main function reads two strings and checks if they are anagrams using areAnagrams.
Limitations:
- This method only works for strings containing lowercase alphabets (‘a’ to ‘z’).
- It cannot handle repeated characters. It only checks if the sets of characters in both strings are the same, not their counts.
- Due to its limitations, this method is not typically used for anagram checking in practical scenarios. Traditional methods like counting or sorting are more versatile and straightforward.
Approach 4: Check if 2 Strings are Anagram in C Example Using Prime Number Multiplication Method
The prime number multiplication method for checking if two strings are anagrams in C is a unique approach. In this method, each letter is assigned a unique prime number, and then each character of the strings is replaced by its corresponding prime number. The product of these numbers for each string is then compared. If the products are the same, the strings are anagrams; otherwise, they are not. Here’s how you can implement it in C:
- Assign Prime Numbers: Assign a unique prime number to each character. Usually, this is done for all lowercase letters ‘a’ to ‘z’. You can extend this to uppercase letters and other characters as needed.
- Calculate String Products: For each string, iterate through its characters and multiply the corresponding prime numbers together.
- Compare Products: If the products for both strings are the same, they are anagrams.
Here’s a sample C code demonstrating this approach:
#include <stdio.h> #include <string.h> #include <stdbool.h> // Assigning prime numbers to lowercase alphabets int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101}; unsigned long long calculateProduct(char *str) { unsigned long long product = 1; for (int i = 0; str[i] != '\0'; i++) { // Assuming the string is in lowercase char c = str[i]; if (c >= 'a' && c <= 'z') { product *= prime[c - 'a']; } } return product; } bool areAnagrams(char *str1, char *str2) { return calculateProduct(str1) == calculateProduct(str2); } int main() { char str1[] = "listen"; char str2[] = "silent"; if (areAnagrams(str1, str2)) printf("The strings are anagrams.\n"); else printf("The strings are not anagrams.\n"); return 0; }
This program assumes the strings contain only lowercase letters. If your strings include uppercase letters or other characters, you must expand the prime[] array and adjust the calculations accordingly.
One thing to be aware of is that this method can be susceptible to integer overflow for very long strings or strings with a high concentration of characters corresponding to large prime numbers. In such cases, you might need to use a data type with a larger capacity than unsigned long long, or implement a different method to handle the multiplication and comparison.
- Pros: Unique and efficient for small character sets.
- Cons: Risk of integer overflow and not practical for large character sets or long strings.
Approach 5: Check if 2 Strings are Anagram in the C Example using the Sorting and Comparing Method.
To check if two strings are anagrams using the sorting and comparing method in C, you follow these steps:
- Sort Both Strings: Arrange the characters in both strings in some order (typically ascending). This can be done using any standard sorting algorithm like quicksort, mergesort, etc.
- Compare Sorted Strings: If the sorted strings are identical, then the original strings are anagrams of each other.
Here’s an example C program using this method:
#include <stdio.h> #include <string.h> // Function to compare two characters (needed for qsort) int compare(const void *a, const void *b) { return *(const char *)a - *(const char *)b; } // Function to check if two strings are anagrams int areAnagrams(char *str1, char *str2) { int n1 = strlen(str1); int n2 = strlen(str2); // If lengths of both strings are not same, they cannot be anagram if (n1 != n2) { return 0; } // Sort both strings qsort(str1, n1, sizeof(char), compare); qsort(str2, n2, sizeof(char), compare); // Compare sorted strings for (int i = 0; i < n1; i++) { if (str1[i] != str2[i]) { return 0; } } return 1; } int main() { char str1[] = "listen"; char str2[] = "silent"; if (areAnagrams(str1, str2)) { printf("'%s' and '%s' are anagrams.\n", str1, str2); } else { printf("'%s' and '%s' are not anagrams.\n", str1, str2); } return 0; }
In this program:
- The compare function is used by qsort to sort the characters in the strings.
- The areAnagrams function first checks if the strings have the same length. If not, they cannot be anagrams.
- It then sorts both strings using qsort.
- Finally, it compares the sorted strings character by character. If any characters differ, the strings are not anagrams.
Note: The sorting approach is straightforward but may not be the most efficient for very long strings, as sorting has a time complexity of O(n log n). This method works well for shorter strings or where simplicity is more important than efficiency.
- Pros: Simple and effective. Works well for any set of characters.
- Cons: Sorting can be less efficient for long strings.
Choosing the Right Approach
The best approach depends on the specific requirements and constraints of your problem:
- For ASCII characters and performance-critical applications, the character count or hash table methods are usually the best.
- For simplicity and smaller strings, sorting and comparing can be effective.
- For alphabetic and case-insensitive characters, bit manipulation is efficient.
- For unique applications or educational purposes, the prime number method is interesting, though not commonly used in production environments.
In the next article, I will discuss the Permutation of String in C Language with Examples. In this article, I explain How to Check if 2 Strings are Anagrams in C Language with Examples. I hope you enjoy this article, Checking if 2 Strings are Anagram in C Language with Examples. I would like to have your feedback. Please post your feedback, questions, or comments about this article.