02-1 : Valid Anagram

Arrays / Hashing

Rohan Morar's photo
Rohan Morar
·

3 min read

Overview

I walk you through how to solve Leetcode problem 242. Valid Anagram. There are various approaches to solving it. This allows us to walk through various trade-offs between time and space complexity respective to each approach, a fundamental skill needed in job interviews.

Key Definition: 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.

Explanation

Approach #1

    def isAnagram(s: str, t: str):
        if len(s) != len(t):
            return False
        sLettersCount, tLettersCount = {}, {}
        for i in range(len(s)):
            sLettersCount[s[i]] = 1 + sLettersCount.get(s[i], 0)
            tLettersCount[t[i]] = 1 + tLettersCount.get(t[i], 0)
        return sLettersCount == tLettersCount

We start by checking if it's the case that the two input strings do not match in length. If this check is true, we can return False because for two words to be anagrams of each other, they must have the same number of characters.

We then create two HashMaps: sLettersCount and tLettersCount which will map the character to the count of the character's appearance in s and t respectively. We can go through the indices of the input string s (it doesn't matter if we choose s or t since their lengths will both be the same).

We then perform the mapping of the letters in both s and t to their respective counts. This is done by updating the sLettersCount and tLettersCount HashMaps and adding 1 to the current count value of that letter. Note, that we get the current count of the letter by using .get(..., 0) to avoid a key not found error.

We complete the approach by returning if the two count HashMaps for s and t are equal, ensuring that s and t are anagrams if True and not anagrams if False.

Time Complexity: O(N)
Space Complexity: O(N)

Approach #2

    def isAnagram(s: str, t: str):
        if len(s) != len(t):
            return False
        l = "abcdefghijklmnopqrstuvwxyz"
        for c in l:
            if s.count(c) != t.count(c):
                return False
        return True

We start by checking if it's the case that the two input strings do not match in length.

We create a string l, of all the letters in the alphabet. We iterate through each letter in the alphabet once and use .count() on the letter for both the s and t input strings. If this check ever returns False, the words are not anagrams. Otherwise, if we check the entire alphabet without returning False, we know the words are anagrams.

This approach has a potential drawback because of the count method being performed twice on two input strings that have very large lengths. In addition, to check for letter variations such as capital letters, symbols, or Unicode characters, we would need to keep updating our l string.

Time Complexity: O(1)
Space Complexity: O(1)

arraysHashing