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


  • 0

    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.


  • 0

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


  • 0

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


  • 0

    @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
    

  • 0

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


  • 0

    @StefanPochmann good eye, i have edited


Log in to reply
 

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