Algorithm: Anagram Checker

Anagram is a word, phrase, or name formed by rearranging the letters of another.

Solution 1: using sort

• sort both strings
• compare the sorted strings

def anagram? (word1, word2)
  return false unless word1.length == word2.length
  word1.downcase.chars.sort == word2.downcase.chars.sort
end

anagram?("cinema", "iceman")

Benchmark for 100.000 characters words: 35.278999999999996 ms

Solution 2: using char frequencies

• create a map
• a map from distinct characters in the word to the number of times they appear.
• compare the occurrences

def frequencies(word)
  frequencies = {}
  word.downcase.chars.each { |char| frequencies[char] = frequencies[char].to_i + 1 }
  frequencies
end

def anagram? (word1, word2)
  frequencies(word1) == frequencies(word2)
end

anagram?("cinema", "iceman")

Benchmark on 100.000 characters words: 72.67999999999999 ms

Solution 3: using prime numbers (for programming languages that supports BigNum)

• assign a prime number to each alphabet letter
• map each character in each word to its prime number
• check that both words have the same product of prime numbers

PRIMES = [
  2, 3, 5, 7, 11, 13, 17,
  19, 23, 29, 31, 37, 41,
  43, 47, 53, 59, 61, 67,
  71, 73, 79, 83, 89, 97, 101
]

ALPHABET = ("a".."z")
DICTIONARY = Hash[*ALPHABET.zip(PRIMES).flatten]

def primes_product(word)
  word.downcase.chars.reduce(1) { |acc, char| DICTIONARY[char] * acc }
end

def anagram? (word1, word2)
  return false unless word1.length == word2.length

  primes_product(word1) == primes_product(word2)
end


anagram?("cinema", "iceman")

Benchmark on 100.000 characters words: 5278.294 ms