VietMX Staff asked 3 years ago
Explain what is space complexity of that solution?
Two words are anagrams of each other if they contain the same number of characters and the same characters. There are two solutions to mention:
- You should only need to sort the characters in lexicographic order, and determine if all the characters in one string are equal to and in the same order as all of the characters in the other string. If you sort either array, the solution becomes
O(n log n). - Hashmap approach where key – letter and value – frequency of letter,
- for first string populate the hashmap
O(n) - for second string decrement count and remove element from hashmap
O(n) - if hashmap is empty, the string is anagram otherwise not.
The major space cost in your code is the hashmap which may contain a frequency counter for each lower case letter from a to z. So in this case, the space complexity is supposed to be constant O(26).
To make it more general, the space complexity of this problem is related to the size of alphabet for your input string. If the input string only contains ASCII characters, then for the worst case you will have O(256) as your space cost. If the alphabet grows to the UNICODE set, then the space complexity will be much worse in the worst scenario.
So in general its O(size of alphabet).
public static bool AreAnagrams(string s1, string s2)
{
if (s1 == null) throw new ArgumentNullException("s1");
if (s2 == null) throw new ArgumentNullException("s2");
var chars = new Dictionary<char, int>();
foreach (char c in s1)
{
if (!chars.ContainsKey(c))
chars[c] = 0;
chars[c]++;
}
foreach (char c in s2)
{
if (!chars.ContainsKey(c))
return false;
chars[c]--;
}
return chars.Values.All(i => i == 0);
}