Valid Anagram

Patrick Leaton
Published: March 16, 2021, 2:24 a.m.
Problem Description

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

 

Description taken from https://leetcode.com/problems/valid-anagram/.

Problem Solution

#Sorting Solution
#O(N log N) Time, O(1) Space
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        return sorted(s) == sorted(t)
 
#HashMap Solution
#O(N) Time, O(N) Space
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        seen_one = seen_two = {}
        for char in s:
            if char in seen_one:
                seen_one[char] += 1
            else:
                seen_one[char] = 1
        for char in t:
            if char in seen_two:
                seen_two[char] += 1
            else:
                seen_two[char] = 1
        return seen_one == seen_two

Problem Explanation

Sorting Solution

The sorting solution is the most straightforward. It is better in space since it requires no external memory, but it is worse on time.

All we need to do is verify that the lengths are the same, then return whether the two sorted strings are the same word.

        if len(s) != len(t):
            return False
        return sorted(s) == sorted(t)

 

HashMap Solution

Two words are an anagram of each other if the frequency of their characters is the same.  Knowing this, we can count the frequency of each character from both strings and place those counts into two different hashmaps.  

If the hashmaps are the same, then the frequency of characters are the same and the words are anagrams of each other.

Let's first verify that the lengths of the strings are the same, if they aren't then they couldn't have the same frequency of characters.

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

 

Otherwise, let's initialize two dictionaries, one for the characters of each string.

        seen_one = seen_two = {}

 

Now we will traverse each character of the first string.

During each iteration, we will check if the current character is in the hashmap.  If it is not, we will place it there with an initial frequency of one.  Otherwise, we will increment its frequency count.

        for char in s:
            if char in seen_one:
                seen_one[char] += 1
            else:
                seen_one[char] = 1

 

We will do the same for the second string and second dictionary.

        for char in t:
            if char in seen_two:
                seen_two[char] += 1
            else:
                seen_two[char] = 1

 

Once we have added all the character counts to both dictionaries, they will be the same if the two strings were anagrams.

        return seen_one == seen_two