Checking if two strings are an anagram

Question

This is my sample code to check if a given pair of strings are anagram or not.

      static bool AreAnagram(string s1, string s2)
      {

        if (s1.Length != s2.Length)
            return false;

        foreach (char c in s1)
        {
            int ix = s2.IndexOf(c);

            if (ix == -1)
                return false;
        }

        return true;
    }

The complexity of this approach is \$O(n)\$.

What boundary conditions am I missing? Can it be made better?

Answer 1

You're missing the case where a word has more than one of the same characters.

For instance, the strings "aba" and "bab" would be seen as an anagram by your algorithm.

You can fix this by removing the found character from the string.

Additionally, if you wanted to make your algorithm faster, you could check if both strings are the same (and return true if they are) before checking the length. This is only a valid option if this is a likely scenario, because otherwise you'll be slowing down each anagram check.

Answer 2

The complexity of your algorithm is \$O(n^2)\$, since IndexOf has complexity \$O(n)\$. You can get a \$O(n\log n)\$ by sorting the two strings and comparing them.

Answer 3

The complexity of this method is actually \$O(n^2)\$, where \$n\$ is s1.Length (which is equal to s2.Length). Let's expand out IndexOf and see why.

foreach (char c in s1)
{
    int ix = -1;
    for (var i = 0; i < s2.Length; i++)
    {
        if (s2[i] == c)
        {
            ix = i;
            break;
        }
    }

    if (ix == -1)
        return false;
}

return true;

As @Pimgd pointed out, it is also incorrect. So how can we fix it? Two strings are anagrams if each character occurs the same number of times, so that seems like a likely approach.

Let's write a method to count the occurrences of each character in a string. We'll use a Dictionary<char, int> to keep track.

private static IDictionary<char, int> GetCharacterCount(string input)
{
    var tally = new Dictionary<char, int>();
    foreach (var c in input)
    {
        int count = tally.TryGetValue(c, out count)
            ? count + 1
            : 1;
        tally[c] = count;
    }

    return tally;
}

Now we want to compare the results of this method

var s1Count = GetCharacterCount(s1);
var s2Count = GetCharacterCount(s2);

foreach (var kvp in s1Count)
{
    var c = kvp.Key;
    if (!s2Count.ContainsKey(c))
    {
        return false;
    }

    if (kvp.Value != s2Count[c])
    {
        return false;
    }
}

return true;

Well, that's one approach, but it seems a bit complicated.

Anagrams have another useful properly, which is that two strings are anagrams of each other if and only if they are equal when they are sorted. So let's convert that into code.

To sort a string, we first have to convert it into a character array, sort the array, and then convert back into a string.

private static string Sort(string input)
{
    var chars = input.ToCharArray();
    Array.Sort(chars);
    return new string(chars);
}

Now we can compare the two sorted sorted strings

var s1Sorted = Sort(s1);
var s2Sorted = Sort(s2);

return s1Sorted == s2Sorted;

Answer 4

In addition to the fine points already made about alternative algorithms, and the incorrect assertion of the \$O(n)\$ performance, there's another condition the original code doesn't handle. And that's characters (really graphemes) that have multiple representations (that is, sequences of char values).

Since you're using C#, you're implicitly using Unicode. You're probably concerned only with the ASCII subset typically used in English, and if so you can ignore the rest of this answer. But if you're looking for a fully general answer, you have to pay attention to other characters. Some characters have multiple ways they can be represented. Some characters can only be represented with more than one sequential char value. For example, from String.Normalize, the character ắ can be represented in three different ways, requiring respectively 1, 2, or 3 char values.

Note that any char-based traversal will lose information; for example treating these the two-character / three char sequences as identical: combining accent + a, e and a, combining accent + e, and treating them differently from accented a, e and a, accented e.

Normalization can convert between these representations. However even normalization cannot turn every character into a single char. Because of this you need to enumerate the characters (which are by necessity themselves each represented as a String). Extract them with StringInfo.GetTextElementEnumerator, then normalize and store a Dictionary of Strings (counting occurrences) per mjolka's approach, or store a List of Strings that you sort and compare using true Unicode-aware sorting and comparisons.

Answer 5

Consider pooling the chars you have and check if you can assemble the second string from them. I am not 100% sure but this should be somewhere between linear and logarithmic in performance.

bool anagramChecker(string first, string second)
{
    if(first.Length != second.Length)
        return false;

    if(first == second)
        return true;//or false: Don't know whether a string counts as an anagram of itself

    Dictionary<char, int> pool = new Dictionary<char, int>();
    foreach(char element in first.ToCharArray()) //fill the dictionary with that available chars and count them up
    {
        if(pool.ContainsKey(element))
            pool[element]++;
        else
            pool.Add(element, 1);
    }
    foreach(char element in second.ToCharArray()) //take them out again
    {
        if(!pool.ContainsKey(element)) //if a char isn't there at all; we're out
            return false;
        if(--pool[element] == 0) //if a count is less than zero after decrement; we're out
            pool.Remove(element);
    }
    return pool.Count == 0;
}

Answer 6

The Dictionary<> is probably a better solution, but if you are interested only in ASCII strings, an array approach is also possible.

 // Returns false if characters out of range.
        static public bool anagramCheckerAsciiOnly(string first, string second)
        {
            if (first.Length != second.Length)
                return false;

            if (first == second)
                return true;

            const int maxValue = 127;
            int[] count = new int[maxValue];

            for (int index = 0; index != first.Length; ++index)
            {
                char a = first[index];
                char b = second[index];
                if (a >= maxValue || b >= maxValue || a < 0 || b < 0)
                    return false;
                ++count[a];
                --count[b];
            }

            return !(count.Any(
                (element) =>
                {
                    return element != 0;
                }
            ));
        }

Answer 7

According to Wikipedia, an anagram can be a word or a phrase. Therefore, white space needs to be dealt with:

public bool AreAnagrams(string one, string two)
{
    var s1 = one.Replace(" ", string.Empty).ToUpper();
    var s2 = two.Replace(" ", string.Empty).ToUpper();

    if (s1.Length != s2.Length)
    {
        return false;
    }

    foreach (var c1 in s1)
    {
        int index = 0;
        if ((index = s2.IndexOf(c1)) > -1)
        {
            s2 = s2.Remove(index, 1);
        }
        else
        {
            return false;
        }
    }
    return true;
}