Valid Anagram

This article will highlight two approaches to this problem

Question

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

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





Constraints:



1 <= s.length, t.length <= 5 * 104

s and t consist of lowercase English letters.

Two approaches

• For both approaches if the length of both strings is not equal return False
  

1. Using Counters

• Create two counters for each string


• loop through each string counting the number of occurrences for each character


• Compare the two counters and return the boolean output

Complexity

Time

𝑂(𝑛)

• loop the two string (s and t) = 𝑂(𝑛) + 𝑂(𝑛)


• insertion into dict counters = 𝑂(1) + 𝑂(1)


• compare dicts = 𝑂(1)

2𝑂(𝑛) + 3𝑂(1) = 𝑂(𝑛)

Space

𝑂(1)

• 2 counters = 𝑂(1) + 𝑂(1)

2𝑂(1)

Code

class Solution:

    def isAnagram(self, s: str, t: str) -> bool:

        if len(s) != len(t):

            return False



        s_counter = {}

        t_counter = {}



        for char in s:

            if char in s_counter:

                s_counter[char] += 1

            else:

                s_counter[char] = 1



        for char in t:

            if char in t_counter:

                t_counter[char] += 1

            else:

                t_counter[char] = 1



        return s_counter == t_counter

2. Using inbuilt sort method

• Use python's inbuilt sorted() method for each string


• Compare if the two sorted strings are equal

Complexity

Time

𝑂(𝑛 log 𝑛 )

• The python's sorted() function uses a Timsort algorithm = 𝑂(𝑛 log 𝑛 ) + 𝑂(𝑛 log 𝑛 )


• compare the two strings = 𝑂(𝑛)

2𝑂(𝑛 log 𝑛 ) + 𝑂(𝑛) = 𝑂(𝑛 log 𝑛 )

Space

𝑂(𝑛)

• Sort function will create a new sorted string from the input string = 𝑂(𝑛) + 𝑂(𝑛)


• compare the two strings = 𝑂(𝑛)

3𝑂(𝑛) = 𝑂(𝑛)

Code

class Solution:

    def isAnagram(self, s: str, t: str) -> bool:

        if len(s) != len(t):

            return False

        return sorted(s) == sorted(t)