-1
\$\begingroup\$

As per WIKI An anagram is direct word switch or word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once; for example, the word anagram can be rearranged into "nag a ram".

What is the Best solution in C# in terms of O(n)? I have below code which works fine with test cases "Debit card", "Bad credit", "Dormitory", "Dirty Room" "The earthquakes", "The queer shake"

public static bool IsAnagram(string input, string anagram)
    {
        //corner cases
        if (string.IsNullOrEmpty(input) || string.IsNullOrEmpty(anagram))
        {
            return false;
        }
        if (input == anagram)
        {
            return false;
        }

        var charMap = new Dictionary<char, int>();
        for (int i = 0; i < input.Length; i++)
        {
            if (!char.IsLetterOrDigit(input[i])) { continue; }
            if (charMap.ContainsKey(char.ToLowerInvariant(input[i])))
            {
                charMap[char.ToLowerInvariant(input[i])]++;
            }
            else
            {
                charMap.Add(char.ToLowerInvariant(input[i]), 1);
            }
        }

        for (int i = 0; i < anagram.Length; i++)
        {
            if (!char.IsLetterOrDigit(anagram[i])) { continue; }

            if (!charMap.ContainsKey(char.ToLowerInvariant(anagram[i])))
            {
                return false;
            }
            if (--charMap[char.ToLowerInvariant(anagram[i])] < 0)
            {
                return false;
            }
        }
        return true;
    }
\$\endgroup\$
3
\$\begingroup\$

Bug:

IsAnagram("AAABBB", "A") //returns true

I would also recommend replacing for loops with foreach loops for better readability. Apart from that, you algorithm looks OK to me.

Linq-based solution is way easier to write:

Func<string, IEnumerable<char>> reorder = 
    s => s.Where(char.IsLetterOrDigit).Select(char.ToLowerInvariant).OrderBy(c => c);
return reorder(input).SequenceEqual(reorder(anagram))

But it will be slower than what you have. Definitely not O(n).

\$\endgroup\$
0
\$\begingroup\$

Convert the string to lower

You are not checking the dictionary for all zero

The cannot be the same if the product is not the same. But that does not guarantee they are the same. And it would still just me O(n).

public static bool IsAnagram(string input, string anagram)
{
    //corner cases
    if (string.IsNullOrEmpty(input) || string.IsNullOrEmpty(anagram))
    {
        return false;
    }
    if (input == anagram)
    {
        return false;
    }

    var charMap = new Dictionary<char, int>();
    foreach (char c in input.Trim().ToLowerInvariant())
    {
        if (!char.IsLetterOrDigit(c)) { continue; }
        if (charMap.ContainsKey(c))
        {
            charMap[c]++;
        }
        else
        {
            charMap.Add(c, 1);
        }
    }

    foreach (char c in anagram.Trim().ToLowerInvariant())
    {
        if (!char.IsLetterOrDigit(c)) { continue; }

        if (!charMap.ContainsKey(c))
        {
            return false;
        }
        if (--charMap[c] < 0)
        {
            return false;
        }
    }

    foreach(int i in charMap.Values)
    {
        if(i != 0)
        {
            return false;
        }
    }
    return true;
}
\$\endgroup\$

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.