DEV Community

Discussion on: Write a script to identify an anagram

Collapse
 
smartyalgo profile image
Michael Ho • Edited

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

Collapse
 
heikodudzus profile image
Heiko Dudzus • Edited

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
Collapse
 
misterysin profile image
MTD

Best answer here. The prime trick is nice but as you said it gets way too expensive very fast.