Check if two strings are anagrams in O(n) time

check_perm.py

# 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