0

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;
}
Improve this question
7
  • 6
    A better fit for codereview.stackexchange.com? Commented Nov 14, 2014 at 18:51
  • 3
    You can get O(n lg n) time if you sort both strings... Commented Nov 14, 2014 at 18:54
  • @Cameron Has the right idea. Sort both strings, then compare character by character. If they match all the way through, they're anagrams. Commented Nov 14, 2014 at 18:57
  • I suspect it is also possible to specialize your sorting algorithm to also check for the anagram, to eliminate the need for the last check. This wouldn't decrease your overall time complexity, however. Commented Nov 14, 2014 at 19:03
  • @JoshKelley Thanks I didnt even know it existed. I'll be sure to post on there in the future. Cameron I did think about that but wasn't sure if the the time to sort both would be worth it. Commented Nov 14, 2014 at 19:04

3 Answers 3

Reset to default
5

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;
}
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

This modifies the strings you pass to the function, though. That might not be expected!
It's better not to trash your arguments... so I would take those &'s off and let IsAnagram work from a local copy. But still: this is a beautiful solution.
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;
}
Improve this answer

2 Comments

+1, very nice. Shouldn't that technically be ..::max() + (std::size_t)1 though? (On the other hand, I guess all of these answers assume ASCII anyway -- anagrams of Unicode encoded into byte strings are much less fun.) And it might be a good idea to allocate it off the stack, in case there's a platform with a wide char and a small stack.
@Cameron - I fixed the +1 issue. Thanks. I realize stack allocation can be a problem on some platforms, but I think I still prefer it for a typical or default algorithm.
1

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.

Improve this answer

4 Comments

Good thinking but you should mention it needs a reasonably modern compiler - is_permutation is C++11
Using the standard library is nice, but note that is_permutation may be up to O(n^2). A custom algorithm can be faster.
@Josh Kelley A custom algorithm can be faster only in a particular case. Otherwise it would be implemented in std::is_permutation.:)
@VladfromMoscow - This is a particular case :-). std::strings are random access containers with small, cheap-to-copy members, so sorting (O(n lg n)) or counting occurrences (O(n)) becomes practical. If performance is important, I'm more comfortable explicitly coding an algorithm than trusting the standard library to optimize for this case.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.