Problem

Given two strings s and t, return true if the two strings are anagrams of each other, otherwise return false.

An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.

Examples

Input: s = "racecar", t = "carrace"

Output: true

Input: s = "jar", t = "jam"

Output: false

Solution

Ideally should yield:

• time complexity: O(n+m)
  • where n is length of s and m is length of t
• space complexity: O(1)

Sort String

Sorting the input strings in alphabetical order, then comparing them as equals.

• Time complexity: O(n log n + m log m)
  • string sort is nominally O(n log n).
  • since we're sorting two strings, we get O(n log n + m log m)
• Space complexity: O(1)

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        sortedStr1 = ''.join(sorted(s))
        sortedStr2 = ''.join(sorted(t))

        if sortedStr2 != sortedStr1:
            return False
        return True

Hash Table Construction

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

        for el in s:
            if el not in str1Ht:
                str1Ht[el] = 1
                pass
            str1Ht[el] += 1

        for el in t:
            if el not in str2Ht:
                str2Ht[el] = 1
                pass
            str2Ht[el] += 1

        if str1Ht == str2Ht:
            return True
        return False