Check Anagram

An anagram is a rearrangement of letters to form another word. Example: "rat" and "tar" are anagrams.

Leetcode link: https://leetcode.com/problems/valid-anagram/

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

We assume the string contains only lowercase alphabets.

Method 1: Sorting#

We can simply convert the string of characters into a list of characters and sort them. Doing so will mean that if the 2 words are actually anagrams, then the list will be exactly the same.

def isAnagram(self, s: str, t: str) -> bool:
if(len(s) != len(t)):
return False
else:
s_arr = list(s) # O(n)
t_arr = list(t) # O(n)
s_arr.sort() # O(nlogn)
t_arr.sort() # O(nlogn)
if(s_arr == t_arr):
return True
return False

Time Complexity#

To calculate the time complexity, we analyse the internal operation of our methods.

The list method which converts our string into a list of characters, will take a total of O(n) time.

The sort method will take O(nlogn) time. Python internally uses a modified Timsort. So overall, we have O(n) + O(n) + O(nlogn) + O(nlogn) time complexity.

Overall, it simplifies to O(nlogn) time complexity.

Useful link for time complexity of common Python methods: https://wiki.python.org/moin/TimeComplexity

Space Complexity#

We use O(n) space to store the characters in lists, where n refers to the length of the string.

Method 2: Counting of Characters#

Another way we can approach the problem is to count the number of times each character appears in the strings. We can do so using a dictionary.

Implementation is omitted as its straightforward:

  1. Put all characters of each string into 2 different dictionaries
  2. Iterate over the characters in each dictionary and check if the count of the character is the same