Checking if two strings are anagrams

Question

Here is my code for checking to see if two strings are anagrams. This seems a little short. Am I missing anything? Both time and space complexity seem to be \$O(1)\$.

//Determine if a string is an anagram
//Time complexity: O(1) 
//Space complexity: O

#include <iostream>
#include <string>
using namespace std;

bool anagram(string one, string two) 
{

    if (one.length() != two.length())
    {   
        return false;
    }

    //sorting the strings
    sort(one.begin(), one.end());
    sort(two.begin(), two.end());

    return (one == two);

}

int main() {

    string one;
    string two;

    cout << "please enter in a string: ";
    cin >> one;
    cout << "please enter in another string: ";
    cin >> two;

    cout << anagram(one, two) <<endl;

    return 0;

}

Answer 1

Dos and donts

Don't use using namespace std. It's fine for very small programs, but std:: immediately tells someone that you're using a standard function and not some self-written sort.

Use all #include's necessary. std::sort is defined in <algorithm>. It seems like your C++ distribution includes <algorithm> or stl_algo in one of the other headers. That's not portable.

Use proper names. anagram doesn't tell anything about the function. Does it create an anagram? Does it check whether something is an anagram of something else? are_anagrams or something similar is less ambiguous.

The issue of \$\mathcal O(1) \$

You cannot get \$\mathcal O(1)\$ for this. You have to view each letter in each word at least once, therefore ending up with \$\mathcal O(n+m)\$ if one.size() \$\mathcal O(n)\$ and two.size() is \$\mathcal O(m)\$. However, since one.size() == two.size() \$n = m\$, otherwise we can find an answer in \$\mathcal O(1) \$.

Regardless, you can solve this in \$\mathcal O(1)\$ additional memory, if you use std::array<int, 128> or another fixed/variable size \$O(1)\$ indexable container:

typedef std::array<int, 256> character_count_type;

bool is_anagram(const std::string & one, const std::string & two)
{
    if(one.size() != two.size())
    {
        return false;
    }
    character_count_type character_count_one;
    character_count_type character_count_two;

    for(std::size_t i = 0; i < one.size(); ++i){
        assert(0 <= one[i] && one[i] < 256);
        assert(0 <= two[i] && two[i] < 256);
        character_count_one[one[i]]++;
        character_count_two[two[i]]++;
    }
    return character_count_one == character_count_two;
}

This has \$\mathcal O(n)\$ worst time complexity, and due to the constant size of std::array<...> \$\mathcal O(1)\$ additional space.