Anagram Program in C++
What is Anagram in String?
When the two strings include the same characters at the same frequency but in a different order, they are said to be anagrams of one another.
For instance, the strings "hello" and "Allah" are anagrams of one another. It is because both strings include the same characters ('he, 'e', 'l', and 'o') at the same frequency,
In a nutshell, both strings include only one instance of the letters "h," "e," and "o" and a pair of the letter "l."
However, if two words like "hello" and "mello" contain distinct sets of characters from one another and do not appear in a different string, then those two strings aren't anagrams of one another.
Method 1 (Use Sorting):
- Sort both strings
- The sorted strings are compared.
Example
#include <bits/stdc++.h>
using namespace std;
bool Anagram(string a1, string a2)
{
int x1 = a1.length();
int x2 = a2.length();
if (x1 != x2)
return false;
sort(a1.begin(), a1.end());
sort(a2.begin(), a2.end());
for (int j = 0; j < x1; j++)
if (a1[j] != a2[j])
return false;
return true;
}
int main()
{
string a1 = "true";
string a2 = "ttew";
if (Anagram(a1, a2))
cout << "The two strings can be converted into anagrams of one another.";
else
cout << "The two strings cannot be converted into anagrams of one another";
return 0;
}
Output
2. Check whether two strings are anagrams of each other by using the std::string::compare() function
- To sort the strings a and b, use the Sort() function.
- To compare strings a and b, use the Compare() function.
Example
#include <bits/stdc++.h>
using namespace std;
int isAnagram(string s1, string s2){
int flag=0;
sort(s1.begin(),s1.end());
sort(s2.begin(),s2.end());
if(s1.compare(s2)==0){
flag=1;
}
else{
flag=0;
}
return flag;
}
int main() {
string s1="tutorials";
string s2="slutortia";
if(isAnagram(s1,s2)==1)
cout<<"YES, They are Anagram"<<endl;
else
cout<<"NO, They are not Anagram"<<endl;
return 0;
}
Output
3.Find the anagram among two strings by counting the frequency:
STEPS:
- Make 256-element count arrays for each of the strings. Create count arrays with all values set to 0.
- Every character in both strings should be iterated through to increase the total number of characters in the appropriate count arrays.
- Arrays of counts for comparison. Return true if the numbers in both count arrays match; if not, return false.
Example
#include <bits/stdc++.h>
using namespace std;
#define NO_OF_CHARS 256
bool areAnagram(char* a1, char* a2)
{
int c1[NO_OF_CHARS] = { 0 };
int c2[NO_OF_CHARS] = { 0 };
int j;
for (j = 0; a1[j] && a2[j]; j++) {
c1[a1[j]]++;
c2[a2[j]]++ }
if (a1[j] || a2[j])
return false;
for (j = 0; j < NO_OF_CHARS; j++)
if (c1[j] != c2[j])
return false;
return true;
}
int main()
{
char a1[] = "null";
char a2[] = "llnu";
if (areAnagram(a1, a2))
cout << "The two strings can be converted into anagrams of one another.";
else
cout << "The two strings cannot be converted into anagrams of one another.";
return 0;
}
Output
4. Using a single count array, determine whether both strings are anagrams of one another:
It could be done to change the example above only to utilize one count array. For characters in str1, increase the value stored in the count array, and reduce it for characters in str2. Finally, both strings are anagrams of one another if all values for the count are 0.
Example
#include <bits/stdc++.h>
using namespace std;
#define NO_OF_CHARS 256
bool Anagram(char* a1, char* a2)
{
int ct[NO_OF_CHARS] = { 0 };
int x;
for (x = 0; a1[x] && a2[x]; x++) {
ct[a1[x]]++;
ct[a2[x]]--;
}
if (a1[x] || a2[x])
return false;
for (x = 0; x < NO_OF_CHARS; x++)
if (ct[x])
return false;
return true;
}
int main()
{
char a1[] = "null";
char a2[] = "llnu";
if (Anagram(a1, a2))
cout <<"The two strings can be converted into anagrams of one another." ;
else
cout << "The two strings cannot be converted into anagrams of one another.";
return 0;
}
Output
5. Utilize a HashMap to store all characters and use it to determine whether both strings are anagrams of one another.
This concept has been modified in that a HashMap holds characters and the number of characters rather than constructing an array of 256 characters according to the original notion. The strategy is to loop over the entire string, store all its characters within a hash table, and then reduce them as needed.
Example
#include <bits/stdc++.h>
using namespace std;
bool isAnagram(string s1, string s2)
{
if (s1.length() != s2.length()) {
return false;
}
unordered_map<char, int> Map;
for (int i = 0; i < s1.length(); i++) {
Map[s1[i]]++;
}
for (int i = 0; i < s2.length(); i++) {
if (Map.find(s2[i]) != Map.end()) {
Map[s2[i]] -= 1;
}
else {
return false;
}
}
for (auto items : Map) {
if (items.second != 0) {
return false;
}
}
return true;
}
int main()
{
string s1 = "null";
string s2 = "lulm";
if (isAnagram(s1, s2))
cout << "The two strings are anagram of each other"
<< endl;
else
cout << "The two strings are not anagram of each "
"other"
<< endl;
}
Output
Conclusion
Anagrams are words or phrases created by reordering the letters of another word or phrase. An anagram of the word string is another string that has precisely the same number of characters in it as the original one, regardless of order. By using these Five methods in C++, we can find whether given two Strings are Anagram or not