# 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

anagramis 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 wordanagramitself can be rearranged intonag a ram, also the wordbinaryintobrainyand the wordadobeintoabode.

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 collections`

class 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.