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.
Is this code \$O(n)\$? I only make one pass per string, but I use a hash Remove which is \$O(n)\$ by itself.
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;
}
Dictionary.Remove()
is O(1), in the average case. \$\endgroup\$