Valid Anagram — Day 62(Python)

Photo by Brett Jordan on Unsplash

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

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

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store