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))
Comments