Leetcode 242: Python Program for Anagrams

This is python program for valid anagram , it explores possible ways to find s and t are valid anagrams.

This program has 10 solutions that explore speed and memory optimization.



import numpy as np

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # solution 1
        # with dictionary and frequency
        #
        """
        1824
        ms
        Beats
        5.78%
        Memory
        19.25
        MB
        Beats
        94.42%
        """
        #s = { k : s.count(k) for k in s }
        #t = { i : t.count(i) for i in t }
        #return s == t 


        # solution 2 with sorting
        #return sorted(s) == sorted(t)

        # solution 3
        """ Runtime :  8  ms Beats 82.33% |   Memory 19.47  MB  Beats 45.25% """

        #return Counter(s) == Counter(t)

        # solution 4
        """ 14  ms    Beats   47.85%  |  Memory  19.37   MB  Beats  75.19%  """ 
        """
        # find map of minimum
        s , t = (t , s ) if len(t) < len(s) else ( s , t ) 
        t = Counter(t)
        seen = Counter()
        for ch in s:    
            if ch not in t:
                # early exit , win 
                return False
            seen[ch] += 1
        # meaning all character are in t
        return seen == t
        """

        # solution 5 , hmm  cat taac
        # no good
        """Runtime 15 ms Beats 44.29% Memory 20.30 MB Beats 17.63%"""
        #ars = bytearray(s.encode("utf-8"))
        #t = bytearray(t.encode("utf-8"))
        #v = sorted(ars ) == sorted( t )
        #return v 

        # solution 6 , hmm 
        """ Runtime 63  ms Beats 5.78% Memory 19.41 MB Beats 45.25%  """
        """
        # Total time:  5.849055014550686e-06
        #start_time = time.perf_counter()
        sc = { ch : 0  for ch in "abcdefghijklmnopqrstuvwxyz"}
        tc = sc.copy()
        for ch in s:
            sc[ch] += 1
        
        for ch in t:
            tc[ch] += 1

        #stime = time.perf_counter()
        #print("Total time: " , stime - start_time )
        return sc == tc   
        """

        # solution 7 , hmm
        """Runtime 11 ms  Beats 77.10% Memory 19.42 MB  Beats 45.25% """


        """
        if len(s) != len(t) : # this was missing
            return False
        # will try to save memory without using Counter first

        sc = {}
        tc = {}
        for ch , cha in zip(s,t ) :
            sc[ch] = sc.get(ch, 0 ) + 1
            tc[cha] = tc.get(cha, 0 ) + 1
 
        return sc == tc

        """
        
        # solution 8 , hmm

        """Runtime 7 ms Beats 91.50% Memory 19.44 MB  Beats 45.25% """
        """
        if len(s) != len(t) : # this was missing
            return False

        #return Counter(s) == Counter(t)

        """
        
 
        # solution 9 , hmm
        # low performance here
        #if len(s) != len(t) : # this was missing
        #    return False
        
        #return sorted(s) == sorted(t)

        # solution 10 
        
        """Runtime 4 ms Beats 95.35% Memory 32.00 MB Beats 9.80 """  


        if len(s) != len(t) : # this was missing
            return False

        s = np.frombuffer(s.encode("ascii") , dtype=np.uint8)
        t = np.frombuffer(t.encode("ascii") , dtype=np.uint8)
        
        # this is fastest solution for scale 

        return np.array_equal(np.sort(s)  , np.sort(t))

Output:



Comments