# Algorithm: Anagram Checker

Posted by

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

### 2 responses to “Algorithm: Anagram Checker”

1. Al B says:

Those were great examples to learn from. THANKS FOR THESE!

2. Andrew says:

Good examples, thanks for sharing.