C++ Check whether two strings are anagram of each other














































C++ Check whether two strings are anagram of each other



Check whether two strings are anagram of each other

Lets first understand what are anagrams. An anagram is a word or phrase formed by rearranging the letters in another word or phrase, such as spar, formed from rasp.

In this problem we will check whether the strings which are given is anagram of each other or not.

Method-1
  • First sort the given strings

  • Then compare the strings if they are same then return true or else fasle

  • Time complexity : O(nlogn)

Implementation

#include <bits/stdc++.h>
using namespace std;

bool checkAnagram(string s1string s2)
{
    // If length of both strings is not same, then they
    // cannot be anagram
    if (s1.length() != s2.length())
        return false;

    // Sort both the strings
    sort(s1.begin(), s1.end());
    sort(s2.begin(), s2.end());

    // Compare sorted strings
    for (int i = 0; i < n1; i++)
        if (s1[i] != s2[i])
            return false;

    return true;
}

int main()
{
    string str1 = "spar";
    string str2 = "rasp";

    if (checkAnagram(str1, str2))
        cout << "The two strings are anagram of each other";
    else
        cout << "The two strings are not anagram of each other";

    return 0;
}



Output
The two strings are anagram of each other

Method-2

  • Create a hashmap mapping char to int.

  •  Store the characters count of string 1 in the hashmap.

  •  Now subtract the character count of string 2 from hashmap, If the count of the character becomes less than 0 that means that character is occurring more number of times in string 2.

  •  Therefore the two strings are not anagrams of each other return false.

  •  Time complexity : O(n)


Implementation

#include <bits/stdc++.h>
using namespace std;

bool checkAnagram(string s1string s2)
{   
    // If length of the str are not same then they are not anagrams
    if (s1.length() != s2.length())
        return false;
    
    // Map to store the count of each character
    map<charintm;
    
    // Insert string 1 character into map
    for (auto i : s1) {
        m[i]++;
    }
    
    // Subtract the string 2 characters from the map
    // If the count become less than 0 that means 
    // that character is occurring more number of times in string 2
    // which means they are not anagrams
    for (auto i : s2) {
        m[i]--;

        if(m[i] < 0
            return false;
    }
    
    return true;
}

int main()  
{
    string str1 = "spar";
    string str2 = "rasp";

    if (checkAnagram(str1str2))
        cout << "The two strings are anagram of each other";
    else
        cout << "The two strings are not anagram of each other";

    return 0;
}

Output
The two strings are anagram of each other

Comments