DEV Community ๐Ÿ‘ฉโ€๐Ÿ’ป๐Ÿ‘จโ€๐Ÿ’ป

DEV Community ๐Ÿ‘ฉโ€๐Ÿ’ป๐Ÿ‘จโ€๐Ÿ’ป is a community of 963,673 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Create account Log in
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

Oldest comments (0)

๐Ÿ‘€ Just want to lurk?

That's fine, you can still create an account and turn on features like ๐ŸŒš dark mode.