Check whether two strings are anagrams using C++

Question

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;
}

Solution 1

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

Solution 2

The algorithm also fails when asked to find if aa and aa are anagrams. Try tracing the steps of the algorithm mentally or in a debugger to find why; you'll learn more that way.

By the way.. The usual method for finding anagrams is counting how many times each letter appears in the strings. The counts should be equal for each letter. This approach has O(n) time complexity as opposed to O(n²).

Solution 3

bool areAnagram(char *str1, char *str2)
{
    // Create two count arrays and initialize all values as 0
    int count1[NO_OF_CHARS] = {0};
    int count2[NO_OF_CHARS] = {0};
    int i;

    // For each character in input strings, increment count in
    // the corresponding count array
    for (i = 0; str1[i] && str2[i];  i++)
    {
        count1[str1[i]]++;
        count2[str2[i]]++;
    }

    // If both strings are of different length. Removing this condition
    // will make the program fail for strings like "aaca" and "aca"
    if (str1[i] || str2[i])
      return false;

    // Compare count arrays
    for (i = 0; i < NO_OF_CHARS; i++)
        if (count1[i] != count2[i])
            return false;

    return true;
}

Solution 4

I see 2 main approaches below:

1. Sort then compare
2. Count the occurrences of each letter

It's interesting to see that Suraj's nice solution got one point (by me, at the time of writing) but a sort one got 22. The explanation is that performance wasn't in people's mind - and that's fine for short strings.

The sort implementation is only 3 lines long, but the counting one beats it square for long strings. It is much faster (O(N) versus O(NlogN)). Got the following results with 500 MBytes long strings.

1. Sort - 162.8 secs
2. Count - 2.864 secs
3. Multi threaded Count - 3.321 secs

The multi threaded attempt was a naive one that tried to double the speed by counting in separate threads, one for each string. Memory access is the bottleneck and this is an example where multi threading makes things a bit worse.

I would be happy to see some idea that would speed up the count solution (think by someone good with memory latency issues, caches).

Solution 5

#include<stdio.h>
#include<string.h>
int is_anagram(char* str1, char* str2){
    if(strlen(str1)==strspn(str1,str2) && strlen(str1)==strspn(str2,str1) &&
    strlen(str1)==strlen(str2))
    return 1;
    return 0;
}
int main(){
    char* str1 = "stream";
    char* str2 = "master";
    if(is_anagram(str1,str2))
    printf("%s and %s  are anagram to each other",str1,str2);
    else
    printf("%s and %s  are not anagram to each other",str1,str2);
    return 0;
}

View more solutions

Comments

[DanielKO]

Even though your 3-liner solution does indeed solve the anagram problem, the OP is clearly having a problem understanding the algorithm. Care to elaborate on why his solution is wrong and why yours is right?

[juanchopanza]

@DanielKO I didn't read OP's algorithm, it seemed too long and over complicated on the surface. I think it should be obvious why this one works, so I didn't explain.

[chris]

@DanielKO, Teaching the OP how to debug it themself would be better, but not practical for an answer (and is not a valid question). This answer does a good job of providing a clean and clear solution.

[M.M]

This causes UB if the string contains negative chars. Also you could halve your memory usage by subtracting from count1 instead of adding to count2.

[typetetris]

What part of the question are you answering to?

[N0dGrand87]

how about test case "ad" vs "bc" which is "97 + 100" vs "98 + 99". Your solution will give false positive result

[NikaTsanka]

Good catch. If I come up with a solution to that I'll edit it. Thanks

[jww]

Also see How to add 2 arbitrarily sized integers in C++?. It provides C++ big integer classes for Botan, Crypto++ and OpenSSL.

[Michael Heidelberg]

It would be helpful if you added an explanation for what the fix was :D

[Monica]

@Gagandeep What is the time complexity of your solution?