You don't need sort or multiply or any fancy stuff
int[26] wordcount; //array containing encounter count of each character.
for each char:
charnum <- ConvertCharToNum(char)
wordcount[charnum]++
return wordcount
Check if the wordcount array of the two strings.
Computation
Does not require to sort, which is nlogn. This only requires a single pass to create wordcount array, thus n.
You can also optimize on aborting upon first index mismatch with this solution (You could also do this with the prime hashing, by aborting on first division yielding a decimal number).
Memory
The 26th prime is 97. Assume it's 100, 6 'z's would be 1006 = 1012. It would take 39 bits, or 5 bytes to store (1012 /log2). This is much less efficient to store a hash. If you want to be stricter, you could store only 1 wordcount, and have the second string count down instead of up.
Feature extension
If I want to accept numbers, the 36th prime is 367 (See Memory). With the array, it's just allocating another 10 index. It is also possible to add this feature without redeploying code, by replacing a specifically allocated array with a map of char to count
This is good. I adapted it to Haskell, recording letter frequencies in Maps/dictionaries. The Map data structure is already an instance of the Eq typeclass, so it was a one-liner to add the equality check:
importqualifiedData.Map.StrictasM-- incrementor for Map entries (used by Map's alter function)incNothing=Just1inc(Justx)=Just(x+1)-- produces a Map containing frequencies of elements in a given list (or Foldable)-- e.g. a Map of frequencies of characters in a given wordfrequencies::(Foldablet,Ordk,Numa)=>tk->M.Mapkafrequencies=foldr(M.alterinc)M.empty-- equality is already defined for Maps :)isAnagramword1word2=frequenciesword1==frequenciesword2
You don't need sort or multiply or any fancy stuff
Check if the wordcount array of the two strings.
Computation
Does not require to sort, which is nlogn. This only requires a single pass to create wordcount array, thus n.
You can also optimize on aborting upon first index mismatch with this solution (You could also do this with the prime hashing, by aborting on first division yielding a decimal number).
Memory
The 26th prime is 97. Assume it's 100, 6 'z's would be 1006 = 1012. It would take 39 bits, or 5 bytes to store (1012 /log2). This is much less efficient to store a hash. If you want to be stricter, you could store only 1 wordcount, and have the second string count down instead of up.
Feature extension
If I want to accept numbers, the 36th prime is 367 (See Memory). With the array, it's just allocating another 10 index. It is also possible to add this feature without redeploying code, by replacing a specifically allocated array with a map of char to count
This is good. I adapted it to Haskell, recording letter frequencies in Maps/dictionaries. The Map data structure is already an instance of the Eq typeclass, so it was a one-liner to add the equality check:
Best answer here. The prime trick is nice but as you said it gets way too expensive very fast.