# Valid Anagram — Day 62(Python)

Today we will be solving an easy tagged question from leetcode. This question is a common question among Bloomberg interviewers.

Given two strings s and t, write a function to determine if t is an anagram of s.

Example 1:

`Input: s = "anagram", t = "nagaram"Output: true`

Example 2:

`Input: s = "rat", t = "car"Output: false`

Note:
You may assume the string contains only lowercase alphabets.

Before we look into the solution, let us understand what exactly is an anagram.

According to Wikipedia,

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. For example, the word anagram itself can be rearranged into nag a ram, also the word binary into brainy and the word adobe into abode.

Okay, let us move to the solution.

We know an anagram is a word that is formed by rearranging the letters of a different word. Why don’t we try sorting the letters in the word and check if both the sorted strings match?

`class AnagramChecker:    def isAnagram(self, s: str, t: str) -> bool:        s = sorted(s)        t = sorted(t)        if s == t:            return True        return False`

Complexity analysis.

Time Complexity

We are using Python’s inbuilt sorting function to sort both the strings. Sorting takes O(nlogn) where n is the length of the string. Post sorting, we are checking if characters match, which takes O(n). Hence the time complexity is O(nlogn). We are assuming the n is the length of the longer string.

Space Complexity.

We are not using any additional data structure to store intermediate results, hence the space complexity is O(1).

Can we try to improve the time complexity? What if we use dictionaries?

We can use two dictionaries to store each character and its frequency. In the end, we can compare both the dictionaries.

`import collectionsclass AnagramChecker:    def isAnagram(self, s: str, t: str) -> bool:        dict_s = collections.Counter(s)        dict_t = collections.Counter(t)        if dict_s == dict_t:            return True        return False`

Complexity analysis.

Time Complexity

We are creating two dictionaries to store the characters and their frequency. And finally, we compare both the dictionaries. The time complexity is O(n).

Space Complexity.

We are creating two dictionaries in this solution, hence the space complexity is O(n+m), where n and m are lengths of the string.

## More from Annamariya Tharayil

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

## Twitter Data Mining and NLP

Get the Medium app