Problem statement
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: s = "anagram", t = "nagaram"
Output: true
Example 2:
Input: s = "rat", t = "car"
Output: false
Approach 1
Since, the letters and their frequency will be same in both strings, we check if they are identical in sorted order. We can return true if they are identical in sorted order.
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return sorted(s) == sorted(t)
Time complexity - O(s log s) or O(t log t)
- due to sorting
Space complexity - O(1)
- if not accounted for the space used for sorting.
Approach 2
We first need to check if their lengths are equal. If not, we can immediately return false as anagrams should be of equal length. Next, we need to count the frequency/occurances of each letter in both strings. We can do that using a hashmap for each string. We can return true if both hashmaps are identical.
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
sMap = {}
tMap = {}
for i in range(len(s)):
sMap[s[i]] = sMap.get(s[i], 0) + 1 #get function on hashMap return it's value
tMap[t[i]] = tMap.get(t[i], 0) + 1 #or default value we specified which is 0 in this case
if len(sMap) != len(tMap): # If lengths of hashMaps are not equal,
return False #it means that there is a mismatch
for c in (sMap):
if(sMap[c] != tMap.get(c, 0)): # In case of t not having a letter present in s,
return False # tMap needs to give 0 there, that's why using get function there.
return True
Time complexity - O(s)
- only single loop.
Space complexity - O(s + t)
- for hashMaps.
Conclusion
Do let me know if I missed any other approach.
Do follow me for more such explanations.
Let's connect on: Twitter LinkedIn Showwcase
Top comments (0)