Check whether two strings are anagram of each other


StringViews 2052

Given two strings s1 and s2, write a function that says whether the two strings are anagram or not s2 is said to be a anagram if it contains same characters that of s1, but order can be different

Example 1

INPUT
s1 = “abcd”
s2 = “cdbe”

OUTPUT
Given two strings are not anagram to each other as the string s1 does not contain all characters of s2

Example 2

s1 = “tutorial cup”
s2 = “cup tutorial”

OUTPUT
Given two strings are anagram to each other

Method 1(using sorting)

Time Complexity : O(nlogn)

Algorithm

1. Sort the both strings

2. Compare the sorted strings

C++ Program

#include <bits/stdc++.h>
using namespace std;
 
//Prototype
void quickSort(char *arr, int start, int end);
int partition(char A[], int start, int end);
 
 
// It will swap two pointers
void swap(char *a, char *b)
{
    char temp;
    temp = *a;
    *a   = *b;
    *b   = temp;
}
//It will sort the given string
void quickSort(char S[], int start, int end)
{
    int pi;    // Partitioning index //
    if(start < end)
    {
        pi = partition(S, start, end);
        quickSort(S, start, pi - 1);
        quickSort(S, pi + 1, end);
    }
} 
int partition(char S[], int start, int end)
{
    char pivot = S[end];
    int i = (start - 1);
    int j;
 
    for (j = start; j <= end - 1; j++)
    {
        if(S[j] <= pivot)
        {
            i++;
            swap(&S[i], &S[j]);
        }
    }
    swap(&S[i + 1], &S[end]);
    return (i + 1);
}
 

// function to check whether two strings are anagram of 
// each other or not 
bool anagrams(char *s1, char *s2)
{
    // Get lenghts of both strings
    int m = strlen(s1);
    int n = strlen(s2);
 
    // If length of both strings is not same, then they 
    // cannot be anagram to each other
    if (m != n)
      return false;
 
    // Sort both strings
    quickSort(s1, 0, m - 1);
    quickSort(s2, 0, n - 1);
 
    // Compare sorted strings
    for (int i = 0; i < m;  i++)
       if (s1[i] != s2[i])
         return false;
 
    return true;
}
 
int main()
{
    char s1[] = "tutorial cup";
    char s2[] = "cup tutorial";
    if (anagrams(s1, s2))
    {
      cout<<"Given two strings are anagram to each other"<<endl;
    }
    else
    {
      cout<<"Given two strings are not anagram to each other"<<endl;
    }
 
    return 0;
}

Try It

Method 2

In this method the main idea is to count the occurences of the characters in both strings and compare them

Algorithm

1. Build two count arrays for s1 and s2.
ie, for example 1
s1_count[‘a’] = 1, s1_count[‘b’] = 1, s1_count[‘c’] = 1, s1_count[‘d’] = 1.
s1_count[‘c’] = 1, s1_count[‘d’] = 1, s1_count[‘b’] = 1, s2_count[‘e’] = 1.

2. Compare two count arrays.
ie, for example 1
s1_count[‘a’] = 1 does not match with s2__count[‘a’](which is 0), so they are not anagram of each other

C++ Program

# include <bits/stdc++.h>
# define NO_OF_CHARS 256

using namespace std;
 
//If the given strings are anagrams, returns true else false
bool anagrams(char *s1, char *s2)
{
    // Build count arrays for s1 and s2
    int s1_count[NO_OF_CHARS] = {0};
    int s2_count[NO_OF_CHARS] = {0};
    int i;
 
    // For each character in input strings, increment count in
    // the corresponding count array
    for (i = 0; s1[i] && s2[i];  i++)
    {
        s1_count[s1[i]]++;
        s2_count[s2[i]]++;
    }
 
    // If any of the two operands is non-zero, then condition becomes true.
    //If any string has more characters ie, s1 is "bfdd" and s2 is "bfd".
    //If the below condition is not present, the function says above s1 and s2 are anagrams
    //but, it is not true
    if (s1[i] || s2[i])
      return false;
 
    // Compare count arrays
    for (i = 0; i < NO_OF_CHARS; i++)
        if (s1_count[i] != s2_count[i])
            return false;
 
    return true;
}
 

int main()
{
    char s1[] = "abcde";
    char s2[] = "acdef";
    if (anagrams(s1, s2))
    {
      cout<<"Given two strings are anagram of each other"<<endl;
    }
    else
    {
      cout<<"The two strings are not anagram of each other"<<endl;
    }
 
    return 0;
}

Try It

 

Translate ยป