Check whether two strings are anagrams using C++

user2688416 picture user2688416 · Aug 16, 2013 · Viewed 38.8k times · Source

The program below I came up with for checking whether two strings are anagrams. Its working fine for small string but for larger strings ( i tried : listened , enlisted ) Its giving me a 'no !'

Help !

#include<iostream.h> 
#include<string.h>
#include<stdio.h>

int main()
{
    char str1[100], str2[100];
    gets(str1);
    gets(str2);
    int i,j;
    int n1=strlen(str1);
    int n2=strlen(str2);
    int c=0;
    if(n1!=n2)
    {
          cout<<"\nThey are not anagrams ! ";
          return 0;
    }
    else 
    {
         for(i=0;i<n1;i++)
             for(j=0;j<n2;j++)
                 if(str1[i]==str2[j])
                     ++c;
    }
    if(c==n1)
        cout<<"yes ! anagram !! ";
    else 
        cout<<"no ! ";

    system("pause");
    return 0;
}

Answer

juanchopanza picture juanchopanza · Aug 16, 2013

I am lazy, so I would use standard library functionality to sort both strings and then compare them:

#include <string>
#include <algorithm>

bool is_anagram(std::string s1, std::string s2)
{
  std::sort(s1.begin(), s1.end());
  std::sort(s2.begin(), s2.end());
  return s1 == s2;
}

A small optimization could be to check that the sizes of the strings are the same before sorting.

But if this algorithm proved to be a bottle-neck, I would temporarily shed some of my laziness and compare it against a simple counting solution:

  1. Compare string lengths
  2. Instantiate a count map, std::unordered_map<char, unsigned int> m
  3. Loop over s1, incrementing the count for each char.
  4. Loop over s2, decrementing the count for each char, then check that the count is 0