242. Valid Anagram - Leetcode Easy

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