Code review, C++, Anagram method

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. Any feedback would be greatly appreciated.

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

This is more efficient generally

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

bool IsAnagram(std::string& str1, std::string& str2)
{
  if(str1.length() != str2.length())
    return false;

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

  return str1.compare(str2) == 0;
}

int main(int argc, char* argv[])
{
  std::string an1("army");
  std::string an2("mary");
  if(IsAnagram(an1, an2)) 
    std::cout << "Hooray!\n";

    return 0;
}

For those who dislike the mutating strings then maybe this is a better option. Could either remove reference to parameters 1 and 2 or make a copy inside function as here. This way, parameters can be const.

bool IsAnagram2(const std::string& str1, const std::string& str2)
{
   if(str1.length() != str2.length())
      return false;

   std::string cpy1(str1), cpy2(str2);

   std::sort(cpy1.begin(), cpy1.end());
   std::sort(cpy2.begin(), cpy2.end());

   return cpy1.compare(cpy2) == 0;
}

Answer 2

There is already standard algorithm std::is_permutation that allows to perform the task simply

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


int main() 
{

    std::string s( "aab" );
    std::string t( "aba" );

    std::cout << std::boolalpha 
              << ( s.size() == t.size() && 
                   std::is_permutation( s.begin(), s.end(), t.begin() ) )
              << std::endl;
    return 0;
}

The output is

true

So all ypu need is to see how the algorithm is realized.:)

If you want a separate function then it will look like

bool IsAnagram( const std::string &s1, const std::string &s2 )
{
    return s1.size() == s2.size() &&
           std::is_permutation( s1.begin(), s1.end(), s2.begin() );
}         

To use std::sort is not a good approach because original strings will be changed or you have to pass them to the function by value.

Answer 3

O(n) algorithm. Instead of sorting (which is O(n lg n)), count up the character occurrences in s1 and compare it to the character occurrences in s2.

#include <string>
#include <iostream>
#include <limits>

bool IsAnagram(const std::string& s1, const std::string& s2)
{
  if (s1.size() != s2.size()) {
    return false;
  }
  int count[std::numeric_limits<char>::max() + (std::size_t)1] = {};
  for (auto c : s1) {
    count[c]++;
  }
  for (auto c : s2) {
    if (!count[c]) {
      return false;
    }
    count[c]--;
  }
  return true;
}

int main(int argc, char **argv)
{
  std::cout << IsAnagram(argv[1], argv[2]) << std::endl;
  return 0;
}