C Tutorial
.
In the realm of programming, understanding algorithms is a crucial aspect. Algorithms dictate how we design and structure our code to solve problems efficiently. Today, we're exploring an interesting algorithm known as the anagram algorithm, specifically an anagram program in C.
The beauty of the anagram algorithm lies in its simplicity and versatility. It is a foundation for various practical applications in cryptography, string manipulation, game development, and much more.
Let's dive deeper into understanding the anagram program in C with explanation and how we can implement it.
An anagram is a type of wordplay, the result of rearranging the letters of a word or phrase to produce a new word or phrase. In programming, two strings are considered anagrams if they can be formed by rearranging the characters of each other, resulting in both strings having the same letters with the same frequencies. For example, the words 'listen' and 'silent' are anagrams of each other.
There are various algorithms to check if two strings are anagrams in C. These methods differ based on their complexity and efficiency. Here, we are going to cover the three most common methods:
1. Sorting and Comparing Method
In this method, the idea is to sort and compare both strings. If the sorted strings are equal, then they are anagrams. Sorting is an operation that puts elements in a sequence arranged according to some comparison operator, and it is performed via the sort_string function in our code. If two strings are anagrams, their sorted forms must be equal.
This method is simple to understand and implement but isn't always the most efficient. Its time complexity depends on the sorting algorithm used. Using a typical comparison-based sorting algorithm like quicksort or mergesort, the time complexity will be O(n log n).
2. Count Characters Method
This approach, sometimes called the count and compared method, involves counting the occurrences of distinct characters in both strings. If the counts are the same for all characters, the two strings are anagrams. This method can be quite efficient because it just requires one traversal through each string and one through the counting array.
This method can be more efficient than the sorting method for certain inputs, but it requires extra space to hold the counts, and it's only effective for character sets of a manageable size. For large character sets (like Unicode), it can be impractical. This method has a time complexity of O(n) but a space complexity of O(1), assuming the length of the string is far less than the total number of characters in the language.
3. Using an Array of Prime Numbers
This method is considered more advanced and is not as commonly used due to the risk of integer overflow and the challenges involved in assigning primes for a large character set. However, it can be very efficient, particularly when the strings are very long and the character set is small.
Each character in the string is assigned a unique prime number, and a value is calculated by multiplying the assigned primes together. Anagrams will have the same value because multiplication is commutative. But, since this multiplication can quickly lead to large numbers, the risk of integer overflow is a real consideration, and this method is only practical for shorter strings and limited character sets. The time complexity of this method is O(n).
Each of these methods has its advantages and disadvantages, and the best one to use depends on the specific requirements of the problem, such as the lengths of the strings and the size of the character set.
To help you better understand, here are some examples of implementing an anagram program in C using the above-mentioned algorithms.
1. Sorting and Comparing Method
Here, we first define a function sort_string to sort a given string. Inside this function, we are using two nested for-loops that simply implement the bubble sort algorithm. We compare each pair of characters in the string and swap them if they are not in order.
The areAnagrams function first sorts both strings using the sort_string function. It then compares the two sorted strings with strcmp, which compares two strings lexicographically and returns 0 if they are equal. Therefore, strcmp(str1, str2) == 0 will be true if the strings are anagrams and false otherwise.
#include <stdio.h>
#include <string.h>
// Function to sort the string
void sort_string(char* s) {
int length = strlen(s);
for(int i = 0; i < length - 1; i++) {
for(int j = i + 1; j < length; j++) {
if(s[i] > s[j]) {
char temp = s[i];
s[i] = s[j];
s[j] = temp;
}
}
}
}
// Anagram function using sorting method
int areAnagrams(char* str1, char* str2) {
sort_string(str1);
sort_string(str2);
return (strcmp(str1, str2) == 0);
} |
2. Count Characters Method
In this method, we first initialise two arrays count1 and count2 to count the frequency of each character in the two strings. The size of the arrays is 256 to account for all possible ASCII characters.
The function areAnagrams counts the occurrences of each character in the two strings simultaneously with the for-loop. If the strings have different lengths, str1[i] || str2[i] will be true, and the function will return 0 (false), indicating that the strings are not anagrams.
Then, the function checks if the character counts are identical for all characters. If they are, the function returns 1 (true), indicating that the strings are anagrams
#include <stdio.h>
#define NO_OF_CHARS 256
// Anagram function using count characters method
int areAnagrams(char* str1, char* str2) {
int count1[NO_OF_CHARS] = {0};
int count2[NO_OF_CHARS] = {0};
int i;
for(i = 0; str1[i] && str2[i]; i++) {
count1[str1[i]]++;
count2[str2[i]]++;
}
if(str1[i] || str2[i])
return 0;
for(i = 0; i < NO_OF_CHARS; i++)
if(count1[i] != count2[i])
return 0;
return 1;
} |
3. Using an Array of Prime Numbers
This method involves associating each alphabet character with a unique prime number. To check if two strings are anagrams, we multiply the primes corresponding to each character in the string. If the results are equal for both strings, then the strings are anagrams. This approach can be efficient, but keep in mind that it can also lead to large numbers and potential integer overflow for long strings.
First, let's assign a prime number to each character. We'll use the first 26 prime numbers for the lowercase English alphabet:
int primes[26] = {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};
The function areAnagrams multiplies the primes corresponding to each character in the strings:
#include <stdio.h>
#include <ctype.h>
// Array of first 26 prime numbers for lowercase English letters
int primes[26] = {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};
// Anagram function using prime numbers
int areAnagrams(char* str1, char* str2) {
long long product1 = 1, product2 = 1;
for(int i = 0; str1[i]; i++)
product1 *= primes[tolower(str1[i]) - 'a'];
for(int i = 0; str2[i]; i++)
product2 *= primes[tolower(str2[i]) - 'a'];
return (product1 == product2);
} |
In the function areAnagrams, product1 and product2 store the product of primes for str1 and str2, respectively. The function tolower is used to convert characters to lowercase so that the program is case-insensitive. The expression tolower(str1[i]) - 'a' gives the index of the character in the alphabet (0 for 'a', 1 for 'b', etc.). This index is used to get the corresponding prime from the prime array.
If product1 and product2 are equal, then str1 and str2 are anagrams, and the function returns 1 (true). Otherwise, the strings are not anagrams, and the function returns 0 (false).
Please note that this method only works for alphabets, and the strings should not contain any non-alphabet characters. Also, be aware of the potential for integer overflow if the strings are very long, as the product of primes can become very large.
Here are a few practice problems to sharpen your understanding of anagrams:
1. Rearranging Anagrams
Given two strings, write a program to check whether we can form the second string by rearranging the characters of the first string.
Hint: You might find the counting characters method helpful for this problem.
2. Anagram Substrings
Given a string, find the number of substrings that are anagrams of each other.
Hint: Consider all possible substrings. Two substrings are anagrams if their character count arrays are identical.
3. Largest Anagram Group
Given an array of words, group the words that are anagrams of each other. Out of these groups, find the largest group of anagrams.
Hint: A hash map could be helpful. The sorted version of a word can be used as the key.
4. Anagram Difference
Given two strings, find out the minimum number of character deletions required to make the two strings anagrams.
Hint: Use the count characters method. The total number of deletions is the sum of the absolute differences in the count of each character in the two strings.
5. Palindrome Anagrams
Given a string, determine if the letters can be rearranged to form a palindrome.
Hint: A palindrome can be formed if, at most, one character occurs an odd number of times in the string.
Remember, the key to mastering programming is consistent practice. Make sure you thoroughly test your solutions and try to think of edge cases that might break your code.
As we have seen, implementing an anagram program in C can be done using various algorithms. Understanding these algorithms not only helps you to become a better programmer, but also prepares you to tackle more complex problems. The algorithm you choose to use depends on the specific requirements of your program and the resources available.
If you found this insightful and are keen on exploring more such intriguing aspects of programming, consider trying out upGrad courses like Full Stack Software Development Bootcamp. They offer in-depth knowledge and practical experience with comprehensive projects to help you navigate the expansive world of coding with ease.
1. What is an Anagram in String?
An anagram refers to a word or phrase that is created by rearranging the letters of another word or phrase, utilising all the original letters only once. In the context of programming, when we say two strings are anagrams, it means that they consist of the same characters, although their order may differ.
2. How many algorithms are used to determine Anagrams in C?
There are several ways to determine if two strings are anagrams in C, including sorting and comparing, count characters method, and using an array of prime numbers.
3. What is the complexity of the Anagram program in C?
The time complexity varies based on the algorithm used. For instance, the sorting method has a complexity of O(n log n), whereas the count characters method has a complexity of O(n).
Leave a Reply
Your email address will not be published. Required fields are marked *