Skip to content

Instantly share code, notes, and snippets.

@rrampage
Last active July 14, 2018 17:11
Show Gist options
  • Save rrampage/48db01c7deacbac26bc8c67a093d7eca to your computer and use it in GitHub Desktop.
Save rrampage/48db01c7deacbac26bc8c67a093d7eca to your computer and use it in GitHub Desktop.
Check if two strings are anagrams in O(n) time
# Check if two strings are permutations (anagrams) of each other
# For this example, using just the lowercase ASCII letters as the alphabet
# Step 1 : Generate k primes using Sieve of Erasthothenes
# Step 2 : Map characters in alphabet to prime
# Step 3 : Compare the products of the 2 strings
# Why does this work?
# - Multiplication is commutative i.e a * b * c = c * a * b
# - Fundamental theorem of arithmetic i.e every natural number can be expressed uniquely as either a prime or a product of primes (https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic)
from string import ascii_lowercase as ALPHABETS
def primes_sieve(limit):
# Generates primes lesser than "limit" using Sieve of Erasthothenes
a = [True] * limit # Initialize the primality list
a[0] = a[1] = False
for n in range(4, limit, 2):
a[n] = False
for (i, isprime) in enumerate(a):
if isprime:
for n in range(i*i, limit, 2*i): # Mark factors non-prime
a[n] = False
return [i for i in range(limit) if a[i]]
PRIMES = primes_sieve(200) # Generates primes lesser than 200. We only need 26 primes. The 26th prime is 101.
mapping = {ALPHABETS[i] : PRIMES[i] for i in range(26)}
def check_perm(a,b):
if len(a) != len(b):
return False
p1 = 1
p2 = 1
for i in range(len(a)):
p1 *= mapping[a[i]]
p2 *= mapping[b[i]]
return p1 == p2
# Some test cases for sanity check
assert(check_perm('hello', 'hello')) # Identity -> a is a permutation of a
assert(check_perm('hello', 'olleh')) # Anagram -> ab is a permutation of ba
assert(not check_perm('worlds', 'world')) # Different length strings cannot be permuations
assert(not check_perm('hello', 'shell')) # Different strings of same length are not permuations
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment