| categories |
|---|
string,array |
One efficient way to programmatically identify if a string t is an anagram of string s is to check if these criteria are met:
- They are of the same length
- For each possible character, the number of occurences in
tis the same as ins
To execute number 2 in linear time, we can use an approach akin to bank accounts. We create an account, then deposit each character in s and withdraw each character in t. In the end, if they are anagrams of each other, we should see in the account that they cancel each other out.
This approach utilizes a table that keeps track of the number of occurences of each character. Then, for each character c found in s, we increment the count of c in the table. Conversely, for each character d in t, we decrement the count of d in the table. To check if they are valid anagrams, each count in the table should be zero.
The choice of how we will represent the table is a factor in the execution time.
A hash map, with the alphabet characters as keys and the occurrence counts as values, would suffice. However, maps tend to require more memory. Read and insert/update operations, although constant time, are also a little slower compared to plain arrays due to it's key-value nature.
An array offers a bit more faster solution. We won't really need to know the characters -- we just need to check the counts for each -- so having the alphabet keys is not necessary. Instead, we can use the position of each character in the alphabet (c - 'a') as index and use an array of integers.