DEV Community 👩‍💻👨‍💻

Bernice Waweru
Bernice Waweru

Posted on

Valid Anagram

Instructions

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

Input: s = "anagram", t = "nagaram"
Output: true
Input: s = "rat", t = "car"
Output: false
Enter fullscreen mode Exit fullscreen mode

Approach

We can sort the given strings and compare if they are equal.

Implementation

def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)
Enter fullscreen mode Exit fullscreen mode

This approach has a time complexity of O(nlog(n)) because of sorting.
The space complexity if O(1)

Approach 2

We can use a hashmap and checking if the count of each letter is the same in both strings.
First we check if the strings have the same length because if they are not of same length we immediately return false.
We initialize a hashmap and iterate through the strings to determine the occurrence of each letter.

def isAnagram(self, s: str, t: str) -> bool:
        lookup = {}
        for i in s:
            if i not in lookup:
                lookup[i] = 1
            else:
                lookup[i] += 1
        for i in t:
            if i in lookup:
                lookup[i] -= 1
            elif i not in lookup or lookup[i] == 0:
                return False

        return True if max(max(lookup.values()), 0) == 0 else False
Enter fullscreen mode Exit fullscreen mode

This has a time complexity of O(n) and space complexity of O(n).

We can also use a set to achieve the same results

def isAnagram(self, s: str, t: str) -> bool:
    if len(s)!=len(t):
       return False
       for i in set(t):
           if s.count(i)<t.count(i):
              return False
       return True
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

Take a look at this:

Settings

Go to your customization settings to nudge your home feed to show content more relevant to your developer experience level. 🛠