# O(n) Python based on the fundamental theorem of arithmetic

• Solution below.

This is based off the fact that prime factors of a number are unique. This means that there is a direct mapping from the prime factors of a number to it's original number. Therefore if we treat each letter as a prime factor, no matter what permutation of the string is presented the product of every factor will equal the same number if they are anagrams. The solution is presented below.

• This is very wrong, for two different reasons. And I doubt this ever got accepted.

• @StefanPochmann you're right it didn't. not sure why i posted it

• @StefanPochmann I have fixed it, this is accepted.

``````class Solution(object):
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
if len(s) != len(t):
return False

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
]
chars = string.ascii_lowercase
map = dict(zip(chars, primes))
comp1 = comp2 = 1

for i in range(len(s)):
comp1 *= map[s[i]]
comp2 *= map[t[i]]

return comp1 == comp2
``````

• That one almost gets accepted. Better make it a habit to copy&paste the entire code as a whole :-) (fixed now)

• @StefanPochmann good eye, i have edited

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.