You don't need sort or multiply or any fancy stuff
int wordcount; //array containing encounter count of each character.
for each char:
charnum <- ConvertCharToNum(char)
Check if the wordcount array of the two strings.
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).
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.
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:
import qualified Data.Map.Strict as M
-- incrementor for Map entries (used by Map's alter function)
inc Nothing = Just 1
inc (Just x) = 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 word
frequencies :: (Foldable t, Ord k, Num a) => t k -> M.Map k a
frequencies = foldr (M.alter inc) M.empty
-- equality is already defined for Maps :)
isAnagram word1 word2 = frequencies word1 == frequencies word2
Best answer here. The prime trick is nice but as you said it gets way too expensive very fast.
We're a place where coders share, stay up-to-date and grow their careers.
We strive for transparency and don't collect excess data.