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

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

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

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay