Initial Solution
class Solution(object):
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
s = sorted(s)
t = sorted(t)
if len(s) != len(t): return False
length = min(len(s), len(t))
for i in range(0, length):
if s[i] != t[i]:
return False
return True
Python
복사
Time and Space Complexity Analysis
Time Complexity: O(n log n)
•
Sorting: Both strings s and t are sorted using Python's built-in sorted() function, which uses Timsort with a time complexity of O(n log n), where n is the length of the string.
•
Comparison: The for loop iterates through the length of the strings once, which takes O(n) time.
•
Overall: Since O(n log n) dominates O(n), the overall time complexity is O(n log n).
Space Complexity: O(n)
•
Sorted arrays: The sorted() function creates new sorted lists for both s and t, each requiring O(n) space.
•
Overall: The space complexity is O(n) due to the additional storage needed for the sorted strings.
Potential Optimization
A more efficient approach would be to use a hash map (dictionary) to count character frequencies, which would achieve O(n) time complexity and O(1) space complexity (assuming a fixed character set like lowercase English letters).
What I didn’t know
•
length difference matters (not knowing meaning of “anagram”)
•
Frequency Count with hashmap
Optimized Solution
class Solution(object):
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
if len(s) != len(t): return False
count = {}
for char in s:
count[char] = count.get(char, 0) + 1
for char in t:
if char not in count:
return False
count[char] -= 1
if count[char] < 0:
return False
return True
Python
복사
Time and Space Complexity Analysis (Optimized)
Time Complexity: O(n)
•
Frequency counting: We iterate through string s once to build the frequency map, which takes O(n) time.
•
Verification: We iterate through string t once to verify the frequencies, which takes O(n) time.
•
Overall: The overall time complexity is O(n), which is more efficient than the sorting approach.
Space Complexity: O(1)
•
Hash map: The hash map stores character frequencies. For a fixed character set (e.g., 26 lowercase English letters), this requires constant space O(1).
•
Overall: The space complexity is O(1) for fixed character sets, or O(k) where k is the number of unique characters.