242. Valid Anagram

Description

See https://leetcode.com/problems/valid-anagram/

Solutions

There are several solutions to this problem. Here are a few of them. I like solution 3 the best as it is the simplest. However, if space is important than solution 2 is the way to go.

Solution 1

Sort the two strings and compare them.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        return sorted(s) == sorted(t)

Space O(N). The sorted function creates new strings. Time is O(N log N) as both strings are sorted.

Solution 2

Since the strings are constrained to lower case English letters an array can be used to store whether or not a letter has been seen. If the strings did not have this constraint (i.e. unicode allowed), then a dict would be used instead.

In this solution the character is turned into its numerical representation. (ASCII uses the first 127 numbers). So we can map the character to an array index (with some math). "a" will be at index 0 and "z" at index 25.

The numerical count of each letter is kept in the array. The count is used rather than a True/False flag because we need to account for duplicate letters.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        chars = [0] * 26
        offset = ord("a")
        for l in s:
            chars[ord(l) - offset] += 1
        for l in t:
            num = ord(l) - offset
            chars[num] -= 1
            if chars[num] < 0:
                return False
        return True

Time is O(N). Space is O(1) (the array is a constant size of 26).

Solution 3

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        return Counter(s) == Counter(t)

Space O(N). This is because two Counter objects are created. Time is O(n) for the equality check (assumption on my part of what equality is doing under the hood).