DEV Community

Cover image for Valid Anagram
BMega
BMega

Posted on

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.

Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay