5
\$\begingroup\$

Two words are anagrams of each other if they contain the same letters, such as "pots == stop".

The easiest way to check is to sort both words, then compare. But that's an \$O(n*log(n))\$ solution and I'd like to find an \$O(n)\$ one.

  1. Is this code \$O(n)\$? I only make one pass per string, but I use a hash Remove which is \$O(n)\$ by itself.

  2. Is there a completely better way? Or can my code be optimized to run faster/cleaner?

public static bool AreAnagrams(string str1, string str2)
{
    //lucky cases
    if(str1 == str2)
        return true;
    if(str1.Length != str2.Length)
        return false;

    Dictionary<char, int> letters = new Dictionary<char, int>();

    //put all the letters for str1 and their occurance in dictionary
    foreach(char c in str1.AsEnumerable<char>())
    {
        if(letters.ContainsKey(c))
            letters[c]++;
        else
            letters[c] = 1;
    }

    //remove matched letters
    foreach(char c in str2.AsEnumerable<char>())
    {
        if(letters.ContainsKey(c))
        {
            letters[c]--;
            if(letters[c] == 0)
                letters.Remove(c);
        }
        //found a letter that wasn't in str1
        else
            return false;
    }

    //true if we added all the letters and removed them all
    return letters.Values.Count == 0;
}
\$\endgroup\$
  • \$\begingroup\$ Dictionary.Remove() is O(1), in the average case. \$\endgroup\$ – svick Apr 13 '12 at 6:54
  • \$\begingroup\$ that's what I get for skimming wikipedia. So then my code is O(n) and as fast as it's going to get? \$\endgroup\$ – jb. Apr 13 '12 at 7:14
  • \$\begingroup\$ For this kind of algorithms I find big O notation misleading. The algorithm is not going to escalate to large N's so, who cares for asymptotic complexity? O(2N) and O(10N) are both O(N), but for n < 10, O(N^2) beats O(10N) Are you going to check anagrams on long words? Don't think so... Bear in mind I'm not saying O(N^2) is not bad, I'm saying that for low N's, the linear factor actually matters because N's order is not that important, so big O is misleading. Correct me if I'm wrong! \$\endgroup\$ – kaoD Apr 20 '12 at 13:00
5
\$\begingroup\$

The Remove call is not necessary - in python:

def anagram(w1, w2):
    from collections import Counter
    counter = Counter()
    for c in w1:
        counter[c] += 1
    for c in w2:
        counter[c] -= 1
    for count in counter.values():
        if count != 0:
            return False
    return True
\$\endgroup\$
4
\$\begingroup\$

Yes, it's probably as fast as it gets (apart from a possible mistake that I'll explain). The average-case complexity of Remove is O(1), and it seems unlikely to me that you could skip any characters in a string since string comparison is O(n) and anagram checking is likely more complex than that. As a first guess, the asymptotic complexity of this algorithm is probably O(n)+O(n^2)=O(n^2) (n^2 because you are doing an O(n) operation for O(n) characters when calling Remove).

The average-case complexity of you algorithm is O(2n)=O(n), which is not bad at all for this problem. I think your implementation is likely to outperform the sorting one because the hash tables behave very well with a low amount of elements (if you mean anagrams in the sense of real words, you will have relatively small inputs).

Now, this line might not do what you intended:

if(str1 == str2)

According to the MSDN, this will compare the values of the strings, not their references, which is already an O(n) operation in itself:

For the string type, == compares the values of the strings.

If your intention was to compare the references (as an easy case), you must cast the strings to object and compare those:

if ((object)str1 == (object)str2)

It's important to note that it doesn't matter from the viewpoint of asymptotic complexity if you are doing an O(n) comparison here, since the O(n^2) later will dominate the complexity anyway. But for amortized complexity it matters, and that is important if you are dealing with small inputs.

\$\endgroup\$
2
\$\begingroup\$
Dictionary<char, int> letters = new Dictionary<char, int>();

If you only need to support the 26 English letters, then using int array of size 26 will be more efficient and produce cleaner code.

\$\endgroup\$
  • \$\begingroup\$ This is a great idea, I suggest you add the full solution I suspect the entire code will be very short and easy. \$\endgroup\$ – Leonid Apr 16 '12 at 0:05
  • 1
    \$\begingroup\$ @Leonid, I'm hesitant to do that because I don't code in C#. The whole thing would be a one liner in my favored language, python. return Counter(w1) == Counter(w2) \$\endgroup\$ – Winston Ewert Apr 17 '12 at 19:20
1
\$\begingroup\$

The use of Remove is not needed though.

You can have something like

if(letters.ContainsKey(c) || letters[c] > 0)
    letters[c]--;
else //found a letter that wasn't in str1
    return false;
\$\endgroup\$
  • \$\begingroup\$ Hmm, one extra unnecessary access. Perhaps if(!letters.ContainsKey(c) || letters[c]-- <= 0) { return false }? But this starts to get a bit criptic. \$\endgroup\$ – ANeves wants peace for Monica Apr 13 '12 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.