CODEWITHSUNDEEP
c++big-oreviewanagram
Tehan Frago
Tehan Frago

Reputation: 21

Code review, C++, Anagram method

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

Upvotes: 0

Views: 499

Answers (3)

Angus Comber
Angus Comber

Reputation: 9708

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

Upvotes: 5

Josh Kelley
Josh Kelley

Reputation: 58362

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

Upvotes: 3

Vlad from Moscow
Vlad from Moscow

Reputation: 311018

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.

Upvotes: 1

Related Questions