Check if two strings are anagrams

Question

I'm doing some practice questions from the book Cracking the coding interview and wanted to get some people to review my code for bugs and optimizations.

Question:

Write a method to decide if two strings are anagrams or not.

/*
Time complexity: O(n^2)
Space complexity: O(n)
*/
bool IsAnagram(std::string str1, std::string str2)
{
    if(str1.length() != str2.length())
        return false;
    for(int i = 0; i < str1.length();i++)
    {
        bool found = false;
        int j = 0;
        while(!found && j < str2.length())
        {
            if(str1[i] == str2[j])
            {
                found = true;
                str2[j] = NULL;
            }
            j++;
        }
        if(!found)
            return false;
    }
    return true;
}

Answer 1

Since you only modify a copy of the second string, the first one should be a const reference:

bool IsAnagram(const std::string &str1, std::string str2)

Also, i and j should be of type size_t to match what they're compared with.

However, I think I'd do it like this:

bool IsAnagram2(std::string str1, std::string str2)
{
    std::sort(str1.begin(), str1.end());
    std::sort(str2.begin(), str2.end());
    return str1==str2;
}

Test program:

#include <iostream>
#include <string>
#include <algorithm>

#define SHOW(x) std::cout << # x " = " << x << '\n'

int main()
{
    std::cout << std::boolalpha;
    SHOW(IsAnagram("\0\0\0\0\0", "\0lehl")); 
    SHOW(IsAnagram("hello", "")); 
    SHOW(IsAnagram("\0\0\0\0\0", "olehl")); 
    SHOW(IsAnagram("hello", "ole")); 
    SHOW(IsAnagram("hello", "plehl")); 
    SHOW(IsAnagram("hello", "hello")); 
    SHOW(IsAnagram("hello", "12345")); 
    SHOW(IsAnagram("hello", "Hello"));
    SHOW(IsAnagram("hello", "oellh"));
    SHOW(IsAnagram("hello", "olelh"));
    SHOW(IsAnagram("hello", "elelh"));
}

Program output

IsAnagram("\0\0\0\0\0", "\0lehl") = true
IsAnagram("hello", "") = false
IsAnagram("\0\0\0\0\0", "olehl") = false
IsAnagram("hello", "ole") = false
IsAnagram("hello", "plehl") = false
IsAnagram("hello", "hello") = true
IsAnagram("hello", "12345") = false
IsAnagram("hello", "Hello") = false
IsAnagram("hello", "oellh") = true
IsAnagram("hello", "olelh") = true
IsAnagram("hello", "elelh") = false

Answer 2

In order to be an anagram, all that is required is that the frequencies of characters in the strings be equal.

/*
 * Time : O(n)
 * Space: O(1)
 */
bool IsAnagram(const std::string &str1, const std::string &str2)
{
    int frequencies[256] {};

    for (int i = 0; i < str1.length(); i++)
    {
        int bucket = (unsigned char) str1[i];
        frequencies[bucket]++;
    }
    for (int i = 0; i < str2.length(); i++)
    {
        int bucket = (unsigned char) str2[i];
        frequencies[bucket]--;
    }

    for (int i = 0; i < 256; i++)
    {
        if (frequencies[i] != 0)
            return false;
    }
    return true;
}

Apologize for any C++ errors, I'm mainly a Java/standard C coder.

Answer 3

Code

I would use two for loops instead of a for loop and a while loop. This way, you shorten your code, and it is more obvious what you are doing. Also, your variable j is initialized as part of the loop and has the scope of the inner loop only, not of the outer loop. You can also remove the found variable this way.

As janos suggested, you should remove the characters when found, not just turn them into NULL; this could significantly speed your search up.

Anagram

You might want to do are convert all strings to lower case. This will allow the input to consist of uppercase and lowercase characters, and still be an anagram if the characters are the same. Also, spaces and punctuation are not always counted as individual anagram characters, so you may wish to remove them.

This is the adjusted loops:

for (int i = 0; i < str1.length(); i++)
{
    for (int j = 0; j < str2.length(); j++)
    {
        if (str1[i] == str2[j])
        {
            str2[j] = NULL;
            break;
        }

        if (j == str2.length() - 1)
            return false;
    }
}

Update

After seeing your question on SO, Cameron's comment gave me an idea. If you #include<algorithm>, you can just do this:

std::sort(str1.begin(), str1.end());
std::sort(str2.begin(), str2.end());
return str1 == str2;

Answer 4

You could remove the found variable. As soon as str1[i] == str2[j] is unequal, you can return false. Return true at the end of the method.

You may want to check if str1 and str2 are initialized (unequal to null).

You could perform the check using a single loop. Compare the character in str1 at i with the character in str2 at length - i - 1.

(Another possible solution was to use the reverse iterator.)

Answer 5

How about holding a (perhaps balanced) BST to lookup chars?

for each char in string1 do:
  insert char into BST and do nothing if it exists

for each char in string2 do:
  lookup char in BST:
    if char doesn't exist in BST:
      return false

return true

Answer 6

This review has come out from beyond the grave, but let's try to put my stone to the building.

---

Reviewing your actual code:

First, you make a early return if the two strings aren't the same size. That's good, probably the first big optimization to do, and yet none of the reviewers did it. Good point for the OP.

• When a parameter doesn't have to change, make it const.
• Don't assign NULL to a char of a string, instead use '\0' in your case.
• Don't compare signed and unsigned types. Use std::size_t for indexes to match the return type of std::string::size() (size_t is in C, while std::size_t is in C++).

---

Reviewing your logic

Your logic is pretty good, very intuitive, congratulation.

Since it's an interview question, (and requirements can be style over speed), you can also consider alternative options:

1. Using a "perfect match" standard algorithm, the STL having a function exactly for this purpose: std::is_permutation (\$O(N^2)\$ in the worst case)

   bool IsAnagramPermutation(const std::string& lhs, const std::string& rhs)
   {
     //return lhs.length() == rhs.length() && std::is_permutation(lhs.cbegin(), lhs.cend(), rhs.cbegin());
     // the following overload is valid since c++14. For c++11 compatible, use the one above.
     return std::is_permutation(lhs.cbegin(), lhs.cend(), rhs.cbegin(), rhs.cend());
   }
   

2. Using standard algorithm for sorting and return if both are same. (\$O(N\log N)\$ in the worst case)

   bool IsAnagramSorting(std::string lhs, std::string rhs)
   {
     if (lhs.length() != rhs.length()) return false;
     std::sort(lhs.begin(), lhs.end());
     std::sort(rhs.begin(), rhs.end());
     return lhs == rhs;
   }
   

3. Building a frequency table and then return false if at least one char has a different count in the two strings. You can vary container type; since the size is known at compile time, I'll choose sts::array (\$O(N)\$ in the worst case?)

   bool IsAnagram(const std::string& lhs, const std::string& rhs)
   {
       const auto length = lhs.length();
       if (length != rhs.length()) return false;
   
       std::array<int, 256> frequencies{};   
       for (std::size_t index = 0; index < length; ++index)
       {
           if (lhs[index] != rhs[index]) {
               ++frequencies[static_cast<unsigned char>(lhs[index])];
               --frequencies[static_cast<unsigned char>(rhs[index])];
           }
       }
       for (auto frequency :  frequencies)
       {
           if (frequency) return false;
       }
       return true;
   }
   

---

Reviewing ... my review !?

In fact, once all little mistakes fixed, the OP method outperforms all other methods (by far) on GCC. On Clang, std::is_permutation and std::sort are both faster, depending on the inputs.

If you want to test it, there's the benchmark. I commented out some bench, because quick-bench can't deal with all cases (timeout).

Once again, before making assumptions, let's measure!

Answer 7

Time complexity here is O(n²), whereas if we sort both the keys first, worst case would be O(n²) and O(n²) which is not really optimized, although it really is easy to write.

    bool isAnagram(string key1,string key2){
    int len=0;
    if(key.length()!=key1.length()){return false;}
    for (int i=0;i<key1.length();i++){
            for (int j=0;j<key1.length();j++){
                if(key1[i]==key2[j]){
                    len++;
                    key2[j] = ' ';//to deal with the duplicates
                    break;
                }
            
            }
        }
if (len==key.length()){return true;}
else{return false;}
}